打家劫舍问题

问题一

这里的原问题可以分解为第n天不偷，和第n天偷的两种情况。

如果第n天偷，则能偷到的最多钱数是dp[n-2] +nums[n]

如果第n天不偷，则能偷到的最多钱数是dp[n-1]

class Solution:
    def rob(self, nums: List[int]) -> int:
        len_nums = len(nums)
        if len_nums == 0:
            return 0
        if len_nums == 1:
            return nums[0]
        dp = [0] * len_nums
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, len_nums):
            dp[i] = max(dp[i-2]+nums[i], dp[i-1])
        return dp[len_nums-1]

围成一圈意味着不可以同时偷首和尾，于是我们只需要将序列分为[0:len(n)-1]和[1:len(n)]两部分即可。

class Solution:
    def rob(self, nums: List[int]) -> int:
        len_nums = len(nums)
        if len_nums == 0:
            return 0
        if len_nums <= 2:
            return max(nums)
        return max(self.max_money(nums[:len_nums-1]),
                   self.max_money(nums[1:len_nums]))
    def max_money(self, target):
        len_tar = len(target)
        dp = len_tar*[0]
        dp[0] = target[0]
        dp[1] = max(target[0],target[1])
        for i in range(2, len_tar):
            dp[i] = max(dp[i-1], dp[i-2]+target[i])
        return dp[-1]

每个结点有两个状态，偷或者是不偷，使用第二维0或1标记，

原问题可以划分为此结点偷，则左右孩子结点可头可不偷

此结点不偷，则左右孩子均不偷

class Solution:
    def rob(self, root: TreeNode) -> int:
        res = self.dp(root)
        return max(res[0], res[1])
    
    def dp(self, root):
        if not(root):
            return [0,0]
        left = self.dp(root.left)
        right = self.dp(root.right)
        
        not_rob = max(left[0],left[1]) + max(right[0],right[1])
        rob = left[0] + right[0] + root.val
        return [not_rob, rob]