算法训练营day41 | {198.打家劫舍, 213.打家劫舍II, 337.打家劫舍III}

第九章动态规划part07，今天是打家劫舍的一天。

198. 打家劫舍

1.1 解题分析

当前房屋偷与不偷取决于前一个房屋和前两个房屋是否被偷了，所以感觉到当前状态和前面状态会有一种依赖关系，这种依赖关系就是动规的递推公式！

将大致思路进一步转化成动规五部曲分析：

  1. dp数组定义：dp[i]表示 考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
  2. 递推公式：
    • 如果偷当前房屋 dp[i] = dp[i - 2] + num[i]
    • 如果不偷当前房屋 dp[i] = dp[i - 1]
    • dp[i] = MAX(dp[i - 2] + num[i], dp[i - 1])
  3. dp数组初始化：
    • 依赖于前两个状态，所以初始化dp[0] = num[0]; dp[1] = MAX(num[0], num[1])
  4. 遍历顺序：从前往后遍历即可
  5. 打印dp数组。

1.2 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}

213. 打家劫舍II

2.1 解题分析

环形问题不好确定起始位置在哪里，终止位置在哪里，把环形展开成一个线形的一个结构，再单独去考虑首元素和尾元素选或不选，由此分析出三种情况：

  • 情况一：考虑不包含首尾元素
  • 情况二：考虑包含首元素，不包含尾元素
  • 情况三：考虑包含尾元素，不包含首元素

注意这里的用词都是“考虑”，例如情况三中，考虑包含尾元素，但不是一定要偷尾部元素。情况二、三已经包含情况一了，分析到这里，本题剩下的部分就和198. 打家劫舍一样了。

2.2 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        int result1 = robRange(nums, 0, nums.length - 2);
        int result2 = robRange(nums, 1, nums.length - 1);
        return Math.max(result1, result2);
    }

    private int robRange(int[] nums, int start, int end) {
        if (start == end) return nums[start];
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }
}

337. 打家劫舍III

3.1 解题分析

与前两个打家劫舍如出一辙，只不过这个换成了树，关键是要讨论当前节点抢还是不抢。

如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子。

3.2 解题小结

3.2.1 暴力递归+记忆化递推

因为递归涉及到重复计算，使用一个map把计算过的结果保存一下，这样如果计算过孙子，那么计算孩子的时候可以复用孙子节点的结果。这种解法属于自顶向下的树形DP。

  • 时间复杂度：O(n)
  • 空间复杂度：O(log n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    Map<TreeNode, Integer> map = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return root.val;
        if (map.get(root) != null) return map.get(root);
        // 偷父节点
        int val1 = root.val;
        if (root.left != null) val1 += rob(root.left.left) + rob(root.left.right);
        if (root.right != null) val1 += rob(root.right.left) + rob(root.right.right);
        // 不偷父节点
        int val2 = rob(root.left) + rob(root.right);
        map.put(root, Math.max(val1, val2));
        return Math.max(val1, val2);
    }
}

3.2.2 动态规划

动态规划使用状态转移容器来记录状态的变化，用一个长度为2的数组，记录当前节点偷与不偷所得到的最大金钱。不用向暴力递归一样，对一个节点偷与不偷得到的最大金钱没有记录，需要实时计算。

递归三部曲：

  1. 返回值和形参：返回值是一个长度为2的数组，保存一个节点偷与不偷两个状态所得到的金钱。参数为当前节点。
  2. 递归的终止条件：当遍历到空节点时，返回 {0，0}
  3. 单层递归逻辑：分别计算偷当前节点能得到的最大金额，不偷当前节点能得到的最大值，以数组的形式返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int rob(TreeNode root) {
        int[] dp = robTree(root);
        return Math.max(dp[0], dp[1]);
    }

    private int[] robTree(TreeNode cur) {
        if (cur == null) return new int[]{0, 0};
        int[] leftDp = robTree(cur.left);
        int[] rightDp = robTree(cur.right);
        // 偷父节点
        int val1 = cur.val + leftDp[0] + rightDp[0];
        // 不偷父节点
        int val2 = Math.max(leftDp[0], leftDp[1]) + Math.max(rightDp[0], rightDp[1]);
        return new int[]{val2, val1};
    }
}

第一遍看视频，没想到的是不偷父节点的时候，左右孩子偷不偷仍然是考虑，隔着位置偷不一定是最好的。

4. 今日收获

  • 打家劫舍，从线性数组、成环到一个二叉树形，关键是想清楚某一个节点偷与不偷，依赖于哪几个节点的状态，从而找到递推关系，使用dp解题。
  • 学习时长：3小时