付費限定文章

一魚多吃 用DP解House Robbery 打家劫舍問題_Leetcode #198_Leetcode 精選75題解析

todd kent on Unsplash

這題也算是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的解題框架

再次複習Dynamic programming的解題框架，可分為三大步驟

1.定義狀態 [我在哪裡]

2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]

1. 定義狀態 [我在哪裡]

DP狀態的定義一開始其實題目沒給，但是沒關係，我們可以試著先定義、推導看看。