213. House Robber II

LeetCode - The World's Leading Online Programming Learning PlatformLeetCode

首尾相接 array，根据不同目的，考虑两种处理方式：

1. 直接loop两遍

2. 根据首位n项的选择与否来分情况解决

这道就是2，把 Q198 稍微改动一下就好了。两个情况是：取了首项不取尾项，取了尾项不取首项。

198. House Robber

class Solution:
    def subMax(self, sub, dp):
        n = len(sub)
        if n == 0: dp[0] = 0
        elif n <= 2: dp[n] = max(sub)
        if n in dp: return dp[n]
        curMax = max(self.subMax(sub[:n-2], dp)+sub[n-1], self.subMax(sub[:n-1], dp))
        dp[n] = curMax
        return curMax    
    
    def rob(self, nums: List[int]) -> int:
        if not nums: return 0
        if len(nums) <= 2: return max(nums)
        dp1, dp2 = dict(), dict()
        return max(self.subMax(nums[:len(nums)-1], dp1), self.subMax(nums[1:], dp2))