化簡無所不在 用學過的DP模型解House Robbery II_Leetcode #213

Frames For Your Heart null on Unsplash

題目敘述 House Robber II

題目會給我們一個nums陣列，分別代表每棟房屋的價值，也就是房屋內有的現金數量。

題目敘述給的情境是假想盜賊要偷東西，限制是相鄰的兩棟房屋不能一起偷，只能選擇其中一棟，否則就會觸發警報器。第一棟和最後一棟也被視為相鄰。

請問盜賊可以得到最大成果是多少?

測試範例

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
​
取中間那棟３得到最大價值。​

Example 2:

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.

取第一棟１和第三棟３，總共得到４為最大價值。​

Example 3:

Input: nums = [1,2,3]
Output: 3

取最後一洞３得到最大價值。

約束條件

Constraints:

• 1 <= nums.length <= 100

輸入陣列長度介於1~100之間。

• 0 <= nums[i] <= 1000

陣列元素(每棟房屋的價值)介於0~1000之間。

觀察　

其實這題和Ｈouse Robbery I 幾乎一樣，只是多了一個頭尾視為相鄰的限制條件。

（也就是說，第一棟和最後一棟是互斥的，不可以同時選。）

換句話說，我們知道有兩種情況：

如果考慮了第一棟，那麼最後一棟不可能被選進來，考慮區間的index相當於０～n-2

如果考慮最後一棟，那麼第一棟不可能被選進來，考慮區間的index相當於１～n-１

目標同樣是掠奪的最大值，所以

掠奪的最大值

＝ Max{ 第一種情況，第二種情況}

＝Max{ 考慮第一棟,　考慮最後一棟}

= Max{ House Robbery I [0~n-2], House Robbery I [1~n-1] }

演算法　化簡到House Robbery I 的ＤＰ模型

承接觀察點的思考，

原本的House Robbery II在經過討論和觀察後，其實就只有兩種情況，

掠奪的最大值

＝ Max{ 第一種情況，第二種情況}

＝Max{ 考慮第一棟,　考慮最後一棟}

= Max{ House Robbery I 房屋區間[0~n-2], House Robbery I 房屋區間[1~n-1] }

把對應的這兩種情況傳入原本我們已經學會的Ｈouse Robbery I的演算法，

再取兩者之間的最大值，就是最終答案，也就是掠奪的最大值。

程式碼　化簡到House Robbery I 的ＤＰ模型

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        def solve( arr ):
            
            dp = {}
            def consider( i ):
                # look-up table
                if i in dp:
                    return dp[i]
                
                # base case
                if i == 0:
                    dp[0] = arr[0]
                    return dp[0]
                
                # base case
                if i == 1:
                    dp[1] = max(arr[0], arr[1])
                    return dp[1]
                
                # general case
                take = arr[i] + consider(i-2)
                skip = 0 + consider(i-1)

                dp[i] = max( take, skip )
                return dp[i]
            # =======================================
            return consider( i = len(arr)-1 )
        # ----------------------------------------------------
        
        if len(nums) == 1:
            return nums[0]
        
        return max( solve(nums[:len(nums)-1]), solve(nums[1:]) )

複雜度分析

時間複雜度:O( n )

一維DP，從第一棟房子逐步遞迴計算到最後一棟房子。

空間複雜度:O(n)

需要建立一張表格value_dp，所佔用空間為O(n)。

關鍵知識點

利用化簡的技巧，發現彼此結構相同，把這題化簡到已經會解的House Robbery I

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

其實這題和Ｈouse Robbery I 幾乎一樣，只是多了一個頭尾視為相鄰的限制條件。

（也就是說，第一棟和最後一棟是互斥的，不可以同時選。）

換句話說，我們知道有兩種情況：

如果考慮了第一棟，那麼最後一棟不可能被選進來，考慮區間的index相當於０～n-2

如果考慮最後一棟，那麼第一棟不可能被選進來，考慮區間的index相當於１～n-１

目標同樣是掠奪的最大值，所以

掠奪的最大值

＝ Max{ 第一種情況，第二種情況}

＝Max{ 考慮第一棟,　考慮最後一棟}

= Max{ House Robbery I [0~n-2], House Robbery I [1~n-1] }

Reference

[1] House Robber II - LeetCode