文章目录

  • 198. 打家劫舍
    • 二维数组
    • 一维数组
  • 213. 打家劫舍II
  • 二维数组
    • 一维数组
  • 337. 打家劫舍III
    • 后序遍历（超时）
    • dp 数组

198. 打家劫舍

题目链接 | 理论基础

经典的 dp 问题，重点在于记录访问过的元素的状态。

二维数组

  1. dp 数组的下标含义：dp[i][j]

    • dp[i][0] 表示不抢房屋 i 的情况下，从房屋 [0, i] 中抢到的最大金额
    • dp[i][1] 表示抢房屋 i 的情况下，从房屋 [0, i] 中抢到的最大金额

  2. dp 递推公式:

    • 不抢房屋 i 的情况：dp[i][0] = max(dp[i-1][0], dp[i-1][1])，从房屋 [0, i – 1] 中选择更优解
    • 抢房屋 i 的情况：dp[i][1] = dp[i-1][0] + nums[i]，则房屋 i – 1 肯定不能抢

  3. dp 数组的初始化：只需要初始化房屋 i=0，其他的值会在递推中更新

    • 对于房屋 0，不抢就是 dp[0][0]=0，抢了就是 dp[0][1]=nums[0]

  4. dp 的遍历顺序：当前房屋 i 完全依赖于 房屋 i – 1 的情况，所以从小到大按顺序遍历即可

  5. 举例推导:

    1231
    00124
    11243
class Solution:def rob(self, nums: List[int]) -> int:# dp[i][0] represents the max money that can be obtained from house [0, i] if house i is not robbed# dp[i][1] represents the max money that can be obatined from house [0, i] if house i is robbeddp = [[0, 0] for _ in range(len(nums))]dp[0][0] = 0dp[0][1] = nums[0]for i in range(1, len(nums)):dp[i][0] = max(dp[i-1][0], dp[i-1][1])dp[i][1] = dp[i-1][0] + nums[i]return max(dp[-1][0], dp[-1][1])

一维数组

实际上，无需在意之前节点进行的状态，也可以直接推导。

  1. dp 数组的下标含义：dp[i] 代表从房屋 [0, i] 中能抢到的最大金额。
  2. dp 递推公式：对于当前的房屋 i，显然有两种选择：抢或者不抢
    • 如果抢了房屋 i，则房屋 i – 1 肯定不能抢，dp[i] = dp[i-2] + nums[i]
    • 如果不抢房屋 i，则房屋 i – 1 可以抢或不抢，dp[i] = dp[i-1]
    • 取最优解即可
  3. dp 数组的初始化：根据递推公式可知，需要初始化 dp[0], dp[1]
    • 只考虑房屋 0 时，dp[0] = nums[0]
    • 考虑房屋 0、1 时，dp[1] = max(nums[0], nums[1])
  4. dp 的遍历顺序：当前房屋 i 完全依赖于 房屋 [0, i – 1] 的情况，所以从小到大按顺序遍历即可
  5. 举例推导：
    nums27931
    dp27111112
class Solution:def rob(self, nums: List[int]) -> int: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-1], dp[i-2] + nums[i])return dp[-1]

213. 打家劫舍II

题目链接 | 理论基础

和上一题的区别在于首尾元素也是相邻的，所以按照上一题的逻辑推到最后一栋房屋时，实际上不能自由根据收益选择是否要抢，还依赖于第一栋房屋的状态。

实际上，分类就可以解决首尾相连的特殊情况：

  1. 第一栋房屋选择不抢，此时最后一栋房屋的状态就完全取决于收益，等价于给定 nums[1:] 进行上一题。
  2. 第一栋房屋选择抢，此时最后一栋房屋肯定不能抢，等价于给定 nums[:-1] 进行上一题。

分别计算两种情况，然后取最大值即可。

二维数组

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

一维数组

同样，其实也不需要保存每一个访问过的房屋的状态，直接记录最佳解即可。

class Solution:def rob(self, nums: List[int]) -> int:if len(nums) == 1:return nums[0]dp_rob1 = [0] * (len(nums))dp_no_rob1 = [0] * (len(nums))# leave house 0 unrobbed, considering nums[1:]dp_rob1[0] = 0dp_rob1[1] = nums[1]for i in range(2, len(nums)):dp_rob1[i] = max(dp_rob1[i-1], dp_rob1[i-2] + nums[i])# rob house 0, leave the last house safe, considering nums[:-1]dp_no_rob1[0] = nums[0]dp_no_rob1[1] = max(nums[0], nums[1])for i in range(2, len(nums) - 1):dp_no_rob1[i] = max(dp_no_rob1[i-1], dp_no_rob1[i-2] + nums[i])dp_no_rob1[-1] = dp_no_rob1[-2]return max(dp_rob1[-1], dp_no_rob1[-1])

337. 打家劫舍III

题目链接 | 理论基础

后序遍历（超时）

朴素的后序遍历，依靠递归解决这道典型的二叉树。但是递归超高的时间复杂度，导致超时，因为递归中有大量的重复计算。

class Solution:def rob(self, root: Optional[TreeNode]) -> int:if root == None:return 0skip_root = self.rob(root.left) + self.rob(root.right)rob_root = root.valif root.left != None:rob_root += self.rob(root.left.left) + self.rob(root.left.right)if root.right != None:rob_root += self.rob(root.right.left) + self.rob(root.right.right)return max(skip_root, rob_root)

dp 数组

很明显，暴力递归对子问题的重复计算导致了超时，所以我们希望使用 dp 来记录已经得到的子问题的最优解，不断递归来得到全局的最优解。由于二叉树需要递归，所以返回值就是用来记录 dp 的（状态，最优解）组合。

递归三部曲：

  1. 递归函数的参数和返回值：
    • 参数只需要当前节点即可
    • 返回值应该是一个大小为 2 的数组 dp，dp[0] 记录了如果不抢当前节点的最大收益，dp[1] 记录了如果抢当前节点的最大收益
  2. 递归的终止条件：对于空节点，必然返回 [0, 0]，因为抢和不抢都是没有收益
  3. 递归的遍历：显然是后序遍历，因为需要先计算左右子节点的 dp 收益
    • 如果偷当前节点，则返回 left_dp[0] + right_dp[0] + root.val
    • 如果不偷当前节点，则返回 max(left_dp[0], left_dp[1]) + max(right_dp[0], right_dp[1])
class Solution:def dpRob(self, root: Optional[TreeNode]) -> [int, int]:# return[0] represents the max money if root is not taken# return[1] represents the max money if root is takenif root == None:return [0, 0]left_dp = self.dpRob(root.left)right_dp = self.dpRob(root.right)skip_root = max(left_dp[0], left_dp[1]) + max(right_dp[0], right_dp[1])rob_root = left_dp[0] + right_dp[0] + root.valreturn [skip_root, rob_root]def rob(self, root: Optional[TreeNode]) -> int:dp_root = self.dpRob(root)return max(dp_root[0], dp_root[1])

树形 dp！一个新的题目，本质还是二叉树 + dp 的组合，就像监控二叉树一样，考察不同知识点的结合掌握。

对于 dp 来说，二叉树的递归性质反而决定了题目更简单，因为递归只允许返回当前节点的状态。
最后一道打家劫舍，终于需要记录访问过的节点状态啦。