[LeetCode刷題練習] Dynamic Programming— House Robber
Published in
2 min readMay 6, 2019
題目連結：
題目類型：
Dynamic Programming
題目說明：
有一個小偷想要偷東西，找到了一列房子，每個房子裡的有不ㄧ樣的財物價值可以偷，但因為防盜系統的關係，你不能偷相鄰兩間房子的物品，請找出最大你能偷的財物價值。
範例一：
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.範例二：
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.我的解法：
這題是比較簡單的dp問題，我使用的解法：
nums 為陣列，dp為當前位置的最大值
- 當陣列無元素時：return 0
- 陣列只有一個元素： return nums[0]
- 陣列大於2個元素：
dp[0] = nums[0] //因為只有一個房子
dp[1] = max( nums[0], nums[1]) //兩間房子時，只能挑一間下手
when 大於兩間房子：
dp[i] = max( dp[i-2] + nums[i], dp[i-1]) // 前一間的最大值或此間與前兩間最大值之和。
程式(C++)：
我是Andy，謝謝你看完這篇文章，如果文章有幫助到你的話，希望不吝於幫我拍手 🙌🙌
