化簡無所不在 用學過的DP模型解House Robbery II_Leetcode #213
題目敘述 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] }
