## [198\. 打家劫舍](https://leetcode-cn.com/problems/house-robber/) > Easy #### 思路 先審題，一般題目問最大的金額，最多的路徑，解的個數之類的問題，很多情況是考察動態規劃。拋開已有認知，還是先分析題目。 * 第一次選擇，可以選任意 * 第二次選擇，不能選擇相鄰位置 這樣的話，暴破得出所有解法， 然后求出和，再進行比較是一種方法，但是應該會TLE，過！需改善思路。 分解問題，以`[2,7,9,3,1]` 為例，從前到后一個房子一個房子搶，分析搶到當前房子能夠搶到的最大，*只考慮到當前，不考慮后面的* ``` i:index, h:代表房子, 箭頭:當前偷到的位置, m:當前位置能偷到的最多的錢 第1步 i 0 1 2 3 4 h 2 7 9 3 1 ↑ m 2 假如只有1個房子那肯定搶 第2步 i 0 1 2 3 4 h 2 7 9 3 1 ↑ m 2 7 到第二個房子，怎么考慮搶或不搶？ 假如拿了h0(第一個房間)就不能拿h1，應為不能拿相鄰的； 那h1比h0值錢，我肯定就放棄h0，搶h1。所以到第二個房間的最多是7 第3步 i 0 1 2 3 4 h 2 7 9 3 1 ↑ m 2 7 11 到第三個房子了，那h2搶不搶? 1. 搶: h2搶，那h1不能搶，取h0位置的能搶的最大和自身位置和，m2 = h2 + m0 = 11 2. 不搶: 那就搶h1，為7 兩種情況取大值，故11 第4步 i 0 1 2 3 4 h 2 7 9 3 1 ↑ m 2 7 11 11 12 后面同理了，簡單過一遍 1. 搶: m3 = h3 + m1 = 3 + 7 = 10 2. 不搶: 11 max(10,11) 故 11 第5步 i 0 1 2 3 4 h 2 7 9 3 1 ↑ m 2 7 11 11 12 1. 搶: m4 = h4 + m2 = 1 + 11 = 12 2. 不搶: 11 max(12,11) 故 12 ``` 那這道題的最終答案就是`m[-1]`，而且我們通過遍歷h列表計算出m列表， 通項公式： `$ i = 0: m[0] = h[0] $` `$ i = 1: m[1] = max(h[0], h[1]) $` `$ i > 1: m[i] = max(h[i]+m[i-2], m[i-1]) $` #### 代碼 python3 ``` class Solution: def rob(self, nums: List[int]) -> int: if len(nums) == 0: return 0 if len(nums) == 1: return nums[0] dp = [0] * len(nums) # base case dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] = max(nums[i] + dp[i-2], dp[i-1]) return dp[-1] ```