任务

198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

思路

dp[i] 表示[0,i]的房屋所能偷窃到的最大金额，根据规则，dp[i] = max(dp[i-2]+nums[i],dp[i-1]))，即选择当前房间或者不选当前房间的最大值作为dp[i]。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) < 2: 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]

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

思路

考虑去掉末尾和去掉开头两种情况，取其中的较大者作为最大金额，其中包含了去掉开头和结尾的情况。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1 : return nums[0]
        notConsiderLast = self.robA(0,len(nums)-1,nums)
        notConsiderFirst = self.robA(1,len(nums),nums)
        return max(notConsiderFirst,notConsiderLast)

    def robA(self,lo,hi,nums):
        if hi-lo == 1: return nums[lo]
        dp = [0] * len(nums)
        dp[lo] = nums[lo]
        dp[lo+1] = max(nums[lo],nums[lo+1])

        for i in range(lo+2,hi):
            dp[i] = max(dp[i-2] + nums[i],dp[i-1])
        
        return dp[hi-1]

337.打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额

思路

考虑树形DP，每个节点向上返回的是选当前节点和不选当前节点的最大值列表。（这个比较难想到），但是想到后整体思路还是比较简单
选当前节点的获得的最大值等于 自己加上不选左右节点
不选当前节点的最大值等于 左右节点（选或不选）的最大值相加

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        return max(self.robTree(root))
    def robTree(self,node):
        if not node: return [0,0]
        
        left = self.robTree(node.left) #左边收集和不收集分别最大的元素
        right = self.robTree(node.right) #右边收集和不收集分别最大的元素
        #选当前node
        val1 = node.val + left[1] + right[1]
        #不选当前node
        val2 = max(left[0],left[1]) +  max(right[0],right[1])

        return [val1,val2]