【代码随想录算法训练营第四十五天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III】

dp数组在这里是抢前i个房屋的最大受益，初始化头两个dp，推导的时候从前往后推，在前一位dp和前两位dp+现在的房子的受益中找最大值。（代码随想录里给了nums=[]，的判断其实不需要，leetcode上给出nums长度大于等于1了。

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

把头和尾分别去掉之后按照上一题的方式计算出一个最大的值，然后再取最大值就可以了。

class Solution:def rob(self, nums: List[int]) -> int:l = len(nums)if l <4:return max(nums)result1 = self.robhouse(nums, 0, l-1)result2 = self.robhouse(nums, 1, l)return max(result1, result2)def robhouse(self, nums, start, end):l = end - startif l<2:return nums[start]dp = [0] * ldp[0] = nums[start]dp[1] = max(nums[start], nums[start+1])for i in range(2, l):dp[i] = max(dp[i-1], dp[i-2]+nums[start+i])return dp[-1]

树形的dp，每次递归返回一个两位的数组，第一位表示偷这个结点的当前最大价值，第二位表示不偷这个节点的当前最大价值，如果结点为None就返回[0,0]。
然后对于每一个结点的子结点进入递归，如果偷这个结点那么返回的最大价值是结点价值+子结点不偷情况的最大价值，如果不偷这个结点则是可以在子结点的偷与不偷情况中选择最大的价值相加返回。

class Solution:def rob(self, root: Optional[TreeNode]) -> int:return max(self.traversal(root))def traversal(self, root):if root == None:return [0, 0] #前面是偷， 后面是不偷left = self.traversal(root.left)right = self.traversal(root.right)return [root.val+left[1]+right[1], max(left)+max(right)]