Day 27 打家劫舍

2025 iThome 鐵人賽

自我挑戰組

Leetcode自學系列第 27 篇

17th鐵人賽

tina0511

2025-10-25 01:22:57

54 瀏覽

分享至

這題剛開始看起來好像只是單純加總問題，但關鍵在於「不能搶相鄰的房子」，所以沒辦法直接用貪心法解。
一開始我有點卡在要怎麼記錄前面的狀態，後來才想到用動態規劃的方式處理。
我用dp[i]代表搶到第 i 間房子時，能拿到的最多金額。每次要不要搶第 i 間，就看「搶前一間」或「搶前兩間再加這間」哪個比較多。這樣就能一步一步往後推，最後dp[n-1]就是答案。