打家持舍的问题主要表现在左右两边如果选择了就不能选择。

198. 打家劫舍

题目描述

image.png

解题思路

  • 确定dp数组（dp table）以及下标的含义

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

  • 确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）
然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
也就是如果偷第i号房间的话，那么假如i-1个房间被偷过，那么就应该为i-2的房间偷过的钱加上偷本号的钱。如果不偷i号房间，那么最大金钱就应该考虑上一个房间。

  • dp数组如何初始化

从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]
从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

  • 遍历顺序

根据递推公式从前向后遍历

  • 举例推导dp数组

以示例二，输入[2,7,9,3,1]为例。
image.png

  1. public int rob(int[] nums) {
  2.     if (nums.length == 0) return 0;
  3.     if (nums.length == 1) return nums[0];
  4.     // dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
  5.     int[] dp = new int[nums.length];
  6.     dp[0] = nums[0];    // 表示到达i的偷窃的最大金钱就问本身
  7.     dp[1] = Math.max(nums[0], nums[1]); // 可偷可不偷，取最大
  9.     for (int i = 2; i < nums.length; i++) {
  10.         //                决定dp[i]的因素就是第i房间偷还是不偷。
  11.         //                如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
  12.         //                如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）
  13.         //                然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
  14.         dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  15.     }
  17.     return dp[nums.length - 1];
  18. }

213. 打家劫舍 II

题目描述

image.png

解题思路

本题的和上一题的区别就是环的问题：
环的问题有三种情况：

  • 去掉尾

image.png

  • 去掉头尾，取中间

image.png

  • 去掉尾巴

image.png
其中情况一和情况三包含了情况二，所以只需要讨论在去掉首和去掉尾的偷的最大金钱。

  1. public int rob(int[] nums) {
  3.     // 不能简单判断是奇数还是偶数
  4.     //            if (nums.length == 0) return 0;
  5.     //            if (nums.length == 1) return nums[0];
  6.     //            // dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
  7.     //            int[] dp = new int[nums.length];
  8.     //            dp[0] = nums[0];    // 表示到达i的偷窃的最大金钱就问本身
  9.     //            dp[1] = Math.max(nums[0], nums[1]); // 可偷可不偷，取最大
  10.     //
  11.     //            if (nums.length % 2 == 1) {
  12.     //                for (int i = 2; i < nums.length - 1; i++) {
  13.     //                    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  14.     //                }
  15.     //                return dp[nums.length - 2];
  16.     //            } else {
  17.     //                for (int i = 2; i < nums.length; i++) {
  18.     //                    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  19.     //                }
  20.     //                return dp[nums.length - 1];
  21.     //            }
  22.     //        }
  24.     if (nums.length == 0) return 0;
  25.     if (nums.length == 1) return nums[0];
  27.     //            情况一：考虑不包含首尾元素
  28.     //            情况二：考虑包含首元素，不包含尾元素
  29.     //            情况三：考虑包含尾元素，不包含首元素
  30.     // 由于情况三和情况二包括了情况一
  31.     int result1 = robRange(nums, 1, nums.length - 1);   // 情况三
  32.     int result2 = robRange(nums, 0, nums.length - 2);   // 情况二
  34.     return Math.max(result1, result2);
  35. }
  37. // 打家持舍抽取dp代码
  38. public int robRange(int[] nums, int start, int end) {
  39.     if (start == end) {
  40.         return nums[start];
  41.     }
  43.     int[] dp = new int[nums.length];
  44.     dp[start] = nums[start];
  45.     dp[start + 1] = Math.max(nums[start], nums[start + 1]);
  47.     for (int i = start + 2; i <= end; i++) {
  48.         dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  49.     }
  51.     return dp[end];
  52. }

337. 打家劫舍 III

题目描述

image.png

解题思路

记忆递归法

本题使用后序遍历，因为需要使用递归结果。将是否把头节点计算作为区分依据。可以使用一个map把计算过的结果保存一下，这样如果计算过孙子了，那么计算孩子的时候可以复用孙子节点的结果。

  1. // 使用map来记录遍历过的值
  2. Map<TreeNode, Integer> map = new HashMap<>();
  4. public int rob(TreeNode root) {
  5.     if (root == null) return 0;
  6.     if (root.left == null && root.right == null) return root.val;
  8.     // 如果哈希表种存在，直接返回
  9.     if (map.containsKey(root)) return map.get(root);
  11.     // 情况一：偷父节点
  12.     int val1 = root.val;
  13.     // 跳过左右孩子计算孙子节点
  14.     if (root.left != null) val1 += rob(root.left.left) + rob(root.left.right);
  15.     if (root.right != null) val1 += rob(root.right.left) + rob(root.right.right);
  17.     // 情况二：不偷父节点
  18.     int val2 = rob(root.left) + rob(root.right);
  20.     int max = Math.max(val1, val2);
  21.     // 放入哈希表
  22.     map.put(root, max);
  24.     // 返回最大的
  25.     return max;
  26. }
  • 时间复杂度：$O(n)$

  • 空间复杂度：$O(\log n)$，算上递推系统栈的空间

    DP

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

这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

  • 终止条件

遇到空节点，直接返回new int[][]{2,2}，也表示初始化。

  • 确定遍历顺序

首先明确的是使用后序遍历。 因为通过递归函数的返回值来做下一步计算。
通过递归左节点，得到左节点偷与不偷的金钱。
通过递归右节点，得到右节点偷与不偷的金钱

  • 确定单层逻辑

如果偷当前节点，那么左右孩子就不能偷。
如果不偷当前节点，那么左右孩子都选最大的偷
最后构造数组返回 。

  • 举例推导dp数组

以示例1为例，dp数组状态如下：（注意用后序遍历的方式推导）
image.png

  1. // 状态标记递归(动态规划)
  2. // 执行用时：0 ms , 在所有 Java 提交中击败了 100% 的用户
  3. // 不偷：Max(左孩子不偷，左孩子偷) + Max(又孩子不偷，右孩子偷)
  4. // root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
  5. // Math.max(rob(root.right)[0], rob(root.right)[1])
  6. // 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
  7. // root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
  8. public int rob(TreeNode root) {
  9.     int[] robTree = robTree(root);
  10.     return Math.max(robTree[0], robTree[1]);
  11. }
  13. // 长度为2的数组，0：不偷，1：偷
  14. public int[] robTree(TreeNode root) {
  15.     if (root == null) {
  16.         return new int[]{0, 0};
  17.     }
  19.     int[] left = robTree(root.left);
  20.     int[] right = robTree(root.right);
  22.     // 选此节点，左右孩子不应该选
  23.     int val1 = root.val + left[0] + right[0];
  24.     // 不选此节点，左右节点应该选择
  25.     int val2 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
  27.     int[] rootArray = new int[2];
  28.     rootArray[0] = val2;
  29.     rootArray[1] = val1;
  30.     return rootArray;
  31. }
  • 时间复杂度：$O(n)$，每个节点只遍历了一次
  • 空间复杂度：$O(\log n)$，算上递推系统栈的空间