团灭 LeetCode 打家劫舍问题

有读者私下问我 LeetCode 「打家劫舍」系列问题(英文版叫 House Robber)怎么做,我发现这一系列题目的点赞非常之高,是比较有代表性和技巧性的动态规划题目,今天就来聊聊这道题目。

打家劫舍系列总共有三道,难度设计非常合理,层层递进。第一道是比较标准的动态规划问题,而第二道融入了环形数组的条件,第三道更绝,把动态规划的自底向上和自顶向下解法和二叉树结合起来,我认为很有启发性。如果没做过的朋友,建议学习一下。

下面,我们从第一道开始分析。

House Robber I

title

  1. public int rob(int[] nums);

题目很容易理解,而且动态规划的特征很明显。我们前文「动态规划详解」做过总结,解决动态规划问题就是找「状态」和「选择」,仅此而已

假想你就是这个专业强盗,从左到右走过这一排房子,在每间房子前都有两种选择:抢或者不抢。

如果你抢了这间房子,那么你肯定不能抢相邻的下一间房子了,只能从下下间房子开始做选择。

如果你不抢这件房子,那么你可以走到下一间房子前,继续做选择。

当你走过了最后一间房子后,你就没得抢了,能抢到的钱显然是 0(base case)。

以上的逻辑很简单吧,其实已经明确了「状态」和「选择」:你面前房子的索引就是状态,抢和不抢就是选择

1

在两个选择中,每次都选更大的结果,最后得到的就是最多能抢到的 money:

  1. // 主函数
  2. public int rob(int[] nums) {
  3. return dp(nums, 0);
  4. }
  5. // 返回 nums[start..] 能抢到的最大值
  6. private int dp(int[] nums, int start) {
  7. if (start >= nums.length) {
  8. return 0;
  9. }
  10. int res = Math.max(
  11. // 不抢,去下家
  12. dp(nums, start + 1),
  13. // 抢,去下下家
  14. nums[start] + dp(nums, start + 2)
  15. );
  16. return res;
  17. }

明确了状态转移,就可以发现对于同一 start 位置,是存在重叠子问题的,比如下图:

2

盗贼有多种选择可以走到这个位置,如果每次到这都进入递归,岂不是浪费时间?所以说存在重叠子问题,可以用备忘录进行优化:

  1. private int[] memo;
  2. // 主函数
  3. public int rob(int[] nums) {
  4. // 初始化备忘录
  5. memo = new int[nums.length];
  6. Arrays.fill(memo, -1);
  7. // 强盗从第 0 间房子开始抢劫
  8. return dp(nums, 0);
  9. }
  10. // 返回 dp[start..] 能抢到的最大值
  11. private int dp(int[] nums, int start) {
  12. if (start >= nums.length) {
  13. return 0;
  14. }
  15. // 避免重复计算
  16. if (memo[start] != -1) return memo[start];
  17. int res = Math.max(dp(nums, start + 1),
  18. nums[start] + dp(nums, start + 2));
  19. // 记入备忘录
  20. memo[start] = res;
  21. return res;
  22. }

这就是自顶向下的动态规划解法,我们也可以略作修改,写出自底向上的解法:

  1. int rob(int[] nums) {
  2. int n = nums.length;
  3. // dp[i] = x 表示:
  4. // 从第 i 间房子开始抢劫,最多能抢到的钱为 x
  5. // base case: dp[n] = 0
  6. int[] dp = new int[n + 2];
  7. for (int i = n - 1; i >= 0; i--) {
  8. dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
  9. }
  10. return dp[0];
  11. }

我们又发现状态转移只和 dp[i] 最近的两个状态有关,所以可以进一步优化,将空间复杂度降低到 O(1)。

  1. int rob(int[] nums) {
  2. int n = nums.length;
  3. // 记录 dp[i+1] 和 dp[i+2]
  4. int dp_i_1 = 0, dp_i_2 = 0;
  5. // 记录 dp[i]
  6. int dp_i = 0;
  7. for (int i = n - 1; i >= 0; i--) {
  8. dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
  9. dp_i_2 = dp_i_1;
  10. dp_i_1 = dp_i;
  11. }
  12. return dp_i;
  13. }

以上的流程,在我们「动态规划详解」中详细解释过,相信大家都能手到擒来了。我认为很有意思的是这个问题的 follow up,需要基于我们现在的思路做一些巧妙的应变。

House Robber II

这道题目和第一道描述基本一样,强盗依然不能抢劫相邻的房子,输入依然是一个数组,但是告诉你这些房子不是一排,而是围成了一个圈

也就是说,现在第一间房子和最后一间房子也相当于是相邻的,不能同时抢。比如说输入数组 nums=[2,3,2],算法返回的结果应该是 3 而不是 4,因为开头和结尾不能同时被抢。

这个约束条件看起来应该不难解决,我们前文「单调栈解决 Next Greater Number」说过一种解决环形数组的方案,那么在这个问题上怎么处理呢?

首先,首尾房间不能同时被抢,那么只可能有三种不同情况:要么都不被抢;要么第一间房子被抢最后一间不抢;要么最后一间房子被抢第一间不抢。

3

那就简单了啊,这三种情况,那种的结果最大,就是最终答案呗!不过,其实我们不需要比较三种情况,只要比较情况二和情况三就行了,因为这两种情况对于房子的选择余地比情况一大呀,房子里的钱数都是非负数,所以选择余地大,最优决策结果肯定不会小

所以只需对之前的解法稍作修改即可:

  1. public int rob(int[] nums) {
  2. int n = nums.length;
  3. if (n == 1) return nums[0];
  4. return Math.max(robRange(nums, 0, n - 2),
  5. robRange(nums, 1, n - 1));
  6. }
  7. // 仅计算闭区间 [start,end] 的最优结果
  8. int robRange(int[] nums, int start, int end) {
  9. int n = nums.length;
  10. int dp_i_1 = 0, dp_i_2 = 0;
  11. int dp_i = 0;
  12. for (int i = end; i >= start; i--) {
  13. dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
  14. dp_i_2 = dp_i_1;
  15. dp_i_1 = dp_i;
  16. }
  17. return dp_i;
  18. }

至此,第二问也解决了。

House Robber III

第三题又想法设法地变花样了,此强盗发现现在面对的房子不是一排,不是一圈,而是一棵二叉树!房子在二叉树的节点上,相连的两个房子不能同时被抢劫,果然是传说中的高智商犯罪:

title

整体的思路完全没变,还是做抢或者不抢的选择,去收益较大的选择。甚至我们可以直接按这个套路写出代码:

  1. Map<TreeNode, Integer> memo = new HashMap<>();
  2. public int rob(TreeNode root) {
  3. if (root == null) return 0;
  4. // 利用备忘录消除重叠子问题
  5. if (memo.containsKey(root))
  6. return memo.get(root);
  7. // 抢,然后去下下家
  8. int do_it = root.val
  9. + (root.left == null ?
  10. 0 : rob(root.left.left) + rob(root.left.right))
  11. + (root.right == null ?
  12. 0 : rob(root.right.left) + rob(root.right.right));
  13. // 不抢,然后去下家
  14. int not_do = rob(root.left) + rob(root.right);
  15. int res = Math.max(do_it, not_do);
  16. memo.put(root, res);
  17. return res;
  18. }

这道题就解决了,时间复杂度 O(N),N 为数的节点数。

但是这道题让我觉得巧妙的点在于,还有更漂亮的解法。比如下面是我在评论区看到的一个解法:

  1. int rob(TreeNode root) {
  2. int[] res = dp(root);
  3. return Math.max(res[0], res[1]);
  4. }
  5. /* 返回一个大小为 2 的数组 arr
  6. arr[0] 表示不抢 root 的话,得到的最大钱数
  7. arr[1] 表示抢 root 的话,得到的最大钱数 */
  8. int[] dp(TreeNode root) {
  9. if (root == null)
  10. return new int[]{0, 0};
  11. int[] left = dp(root.left);
  12. int[] right = dp(root.right);
  13. // 抢,下家就不能抢了
  14. int rob = root.val + left[0] + right[0];
  15. // 不抢,下家可抢可不抢,取决于收益大小
  16. int not_rob = Math.max(left[0], left[1])
  17. + Math.max(right[0], right[1]);
  18. return new int[]{not_rob, rob};
  19. }

时间复杂度 O(N),空间复杂度只有递归函数堆栈所需的空间,不需要备忘录的额外空间。

你看他和我们的思路不一样,修改了递归函数的定义,略微修改了思路,使得逻辑自洽,依然得到了正确的答案,而且代码更漂亮。这就是我们前文「不同定义产生不同解法」所说过的动态规划问题的一个特性。

实际上,这个解法比我们的解法运行时间要快得多,虽然算法分析层面时间复杂度是相同的。原因在于此解法没有使用额外的备忘录,减少了数据操作的复杂性,所以实际运行效率会快。

坚持原创高质量文章,致力于把算法问题讲清楚,欢迎关注我的公众号 labuladong 获取最新文章:

labuladong

上一篇:团灭 LeetCode 股票买卖问题

下一篇:动态规划之四键键盘

目录