動機

雖然說是環狀，但當成一般有終點的就好

同時，dp最好從終點去推!!

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

Example 1:

Input: nums = [1,2,3,1]Output: 4Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]Output: 12Explanation: 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.

 

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Sol

環狀代表任何一個地方都是起點，任何一個地方都是終點

有兩個dp，一個是用起點去算最多$$的路徑，因為環狀，所以不用全走只要走一半就好

class Solution:
    @functools.lru_cache(None)
    def dp(self,i):
        if i < len(self.ns):
            return self.ns[i] + max([self.dp(x) for x in range(i+2,i+2+len(self.ns)//2)])
        else:
            return 0
    def rob(self, nums: List[int]) -> int:
        self.ns = nums
        if len(nums) <= 2:
            return max(nums)
        else:
            return max([self.dp(x) for x in range(len(nums)//2+1)]) # 要+1，不然像長度為3就只會看第一個不會看第二個!!

另一個是終點去算最多$$的路徑，這code簡單又不容易出錯

class Solution:
    @functools.lru_cache(None)
    def dp(self,i):
        if 0 <= i < len(self.ns):
            return max(self.ns[i] + self.dp(i-2), self.dp(i-1))
        else:
            return 0
    def rob(self, nums: List[int]) -> int:
        self.ns = nums
        return self.dp(len(nums)-1)