今日专题 ：动态规划、打家劫舍
总结：
198. 打家劫舍
class Solution:
def rob(self, nums: List[int]) -> int:
#dp[n]=max(dp[n-1],dp[n-2]+nums[n])
size=len(nums)
if size==1:
return nums[0]
#n的状态只依赖n-1和n-2的状态，对状态进行压缩
i,j=nums[0],max(nums[0],nums[1])
result=max(i,j)
for n in range(2,size):
result=max(j,i+nums[n])
i,j=j,result
return result
213. 打家劫舍 II
思路：环形的打家劫舍
class Solution:
def rob(self, nums: List[int]) -> int:
# 环形的打家劫舍
# 计算两个最大值 偷0 和不偷0
# 偷0 则dp从2开始 size-2
# 不偷0 dp从1开始到 size-1
def robs(numList):
if len(numList) < 2:
return numList[0]
i, j = 0, 0
res = j
for n in numList:
res = max(j, i + n)
i, j = j, res
return res
size = len(nums)
if size <= 3:
return max(nums)
return max(robs(nums[2 : size - 1]) + nums[0], robs(nums[1:]))
337. 打家劫舍 III
思路：关键点在于把当前层选没选传递下去
1.如果上层节点没有被选，则当前节点可选可不选取最大值
2.如果上层节点被选，则当前节点只能不选
总结：以下解法一为我根据上述思路做出来的解法，其实不属于动态规划解法，每个节点被遍历两次，解法二从下往上返回不同选择的结果，并用子问题的结果一步步构建到根节点的结果
解法一：
# 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:
# 树形打家劫舍
@cache
def dfs(node, flag):
if node == None:
return 0
res1, res2 = 0, 0
if node.left:
res1 += dfs(node.left, False)
if node.right:
res1 += dfs(node.right, False)
if not flag:
res2 += node.val
if node.left:
res2 += dfs(node.left, True)
if node.right:
res2 += dfs(node.right, True)
return max(res1, res2)
return dfs(root, False)
解法二
# 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:
# dp数组（dp table）以及下标的含义：
# 1. 下标为 0 记录 **不偷该节点** 所得到的的最大金钱
# 2. 下标为 1 记录 **偷该节点** 所得到的的最大金钱
dp = self.traversal(root)
return max(dp)
# 要用后序遍历, 因为要通过递归函数的返回值来做下一步计算
def traversal(self, node):
# 递归终止条件，就是遇到了空节点，那肯定是不偷的
if not node:
return (0, 0)
left = self.traversal(node.left)
right = self.traversal(node.right)
# 不偷当前节点, 偷子节点
val_0 = max(left[0], left[1]) + max(right[0], right[1])
# 偷当前节点, 不偷子节点
val_1 = node.val + left[0] + right[0]
return (val_0, val_1)