代码随想录第34天：动态规划7（打家劫舍问题：链式、环式、树式房屋）

一、背包问题小结

1.递推公式：

1.问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

2.问装满背包有几种方法：dp[j] += dp[j - nums[i]] 

3.问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

4.问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j])

2.遍历顺序：

1.01背包：“二维”顺序随便，“一维”只能先物品后背包，且背包逆序遍历

2.完全背包：先物品后背包求组合，先背包后物品求排列。

二、打家劫舍（Leetcode 198）

1.确定dp数组以及下标的含义

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

2.确定递推公式

偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间，那么dp[i] = dp[i - 1]

dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

3.dp数组初始化

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

4.确定遍历顺序

dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，从前到后遍历

class Solution:def rob(self, nums: List[int]) -> int:# 边界情况处理：如果没有房子，收益为 0if len(nums) == 0:return 0# 如果只有一间房子，直接抢它if len(nums) == 1:return nums[0]# 初始化 DP 数组，长度为 len(nums) + 1，dp[i] 表示抢前 i 个房子的最大金额dp = [0] * (len(nums) + 1)# 初始化前两个状态：# dp[0] 实际代表抢第 0 个房子的最大收益（即 nums[0]）# dp[1] 是抢第 0 和第 1 个房子中最大值（只能选一个）dp[0], dp[1] = nums[0], max(nums[0], nums[1])# 从第三个房子开始迭代for i in range(2, len(nums)):# 状态转移方程：# 要么不抢当前房子（dp[i - 1]），要么抢当前房子加上 i-2 的最优值（dp[i - 2] + nums[i]）dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])# 返回抢到最后一间房子的最大收益return dp[len(nums) - 1]

空间优化版：将O（N）复杂度优化为O（1）

class Solution:def rob(self, nums: List[int]) -> int:# 边界处理：如果没有房子可抢if not nums:return 0# 如果只有一间房子，直接返回其金额if len(nums) == 1:return nums[0]# 初始化两个变量用于存储前两个位置的最大收益prev2 = nums[0]                    # dp[i - 2]，抢第0间房子的最大收益prev1 = max(nums[0], nums[1])      # dp[i - 1]，前两间房子中选择收益最大的# 从第3间房子开始遍历for i in range(2, len(nums)):# 状态转移：要么不抢当前房子（继承上一个的最大值），# 要么抢当前房子（加上前前一间房子的最大值）curr = max(prev1, prev2 + nums[i])# 更新状态，为下次迭代准备prev2, prev1 = prev1, curr# 最终的最大收益在 prev1 中return prev1

三、打家劫舍（Leetcode 213）

思路：因为首尾相邻，所以我们不能同时选择第一间和最后一间。所以将问题拆解为两个子问题：

1. 抢劫第 0 ~ n-2 间房（不包含最后一间）————>  nums[:n - 1]

2. 抢劫第 1 ~ n-1 间房（不包含第一间）————> nums[1:]

两者取最大值即可。相当于利用”打家劫舍198题“算2次取max

class Solution:def rob(self, nums: List[int]) -> int:# 如果输入列表为空，返回0，因为没有房屋可以抢劫if len(nums) == 0:  return 0# 如果列表只有一个房屋，返回该房屋的金额if len(nums) == 1: return nums[0]# 定义一个辅助函数，解决线性排列的房屋抢劫问题def solve(arr):# pre_2 表示前两个房屋的最大抢劫金额，pre_1 表示前一个房屋的最大抢劫金额pre_2, pre_1 = 0, 0# 遍历数组中的每个房屋for i in arr:# 当前房屋的最大金额 = max(不抢当前房屋只取前一个，抢当前房屋加上前两个)cur = max(pre_1, pre_2 + i)# 更新 pre_2 和 pre_1，为下一次迭代做准备pre_2, pre_1 = pre_1, cur# 返回最后一个房屋考虑后的最大金额return pre_1# 由于首尾房屋不能同时抢劫，比较两种情况：# 1. 抢劫从第2个房屋到最后一个房屋（nums[1:]）# 2. 抢劫从第1个房屋到倒数第二个房屋（nums[:-1]）# 取两者的最大值return max(solve(nums[1:]), solve(nums[:-1]))

def solve(arr):pre_2, pre_1 = 0, 0for i in arr:cur = max(pre_1, pre_2 + i)pre_2, pre_1 = pre_1, curreturn pre_1

为什么不返回 cur？
因为 cur 是临时变量，它是当前轮次刚计算出来的值，更新完之后才赋值给 pre_1。

而 pre_1 一直记录的是截至当前位置的最优解，是我们想要的答案。

四、打家劫舍（Leetcode 337）

1.确定递归函数的参数和返回值

这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。

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 = rightclass Solution:def rob(self, root: Optional[TreeNode]) -> int:# 定义辅助函数，返回一个元组 (rob, not_rob)# rob: 抢劫当前节点时的最大金额# not_rob: 不抢劫当前节点时的最大金额def dfs(node):# 基本情况：如果节点为空，返回 (0, 0)if not node:return 0, 0# 递归处理左子树和右子树left_rob, left_not_rob = dfs(node.left)right_rob, right_not_rob = dfs(node.right)# 抢劫当前节点：不能抢劫左右子节点，取左右子节点的 not_rob 值rob_current = node.val + left_not_rob + right_not_rob# 不抢劫当前节点：可以选择抢或不抢左右子节点，取最大值not_rob_current = max(left_rob, left_not_rob) + max(right_rob, right_not_rob)# 返回当前节点的两种情况的最大金额return rob_current, not_rob_current# 调用 dfs，返回抢或不抢根节点的最大值rob_root, not_rob_root = dfs(root)return max(rob_root, not_rob_root)