[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,謝謝你看完這篇文章,如果文章有幫助到你的話,希望不吝於幫我拍手 🙌🙌