這題也算是Leetcode 上經典的DP考題之一,也是很好的DP邏輯思考練習題。
題目會給我們一個nums陣列,分別代表每棟房屋的價值,也就是房屋內有的現金數量。
題目敘述給的情境是假想盜賊要偷東西,限制是相鄰的兩棟房屋不能一起偷,只能選擇其中一棟,否則就會觸發警報器。
請問怎麼選擇哪幾棟房屋下手,可以得到最大成果?
Example 1:
Input: nums = [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.
挑第一棟和第三棟房屋,得到總價值為1+3=4
Example 2:
Input: nums = [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.
挑第一棟、第三棟和第五棟房屋,得到總價值為2+9+1=12
Constraints:
1 <= nums.length <= 100
輸入陣列長度介於1~100之間。
0 <= nums[i] <= 400
陣列元素(每棟房屋的價值)介於0~400之間。
再次複習Dynamic programming的解題框架,可分為三大步驟
1.定義狀態 [我在哪裡]
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走,怎麼出發的]
DP狀態的定義一開始其實題目沒給,但是沒關係,我們可以試著先定義、推導看看。