lt.198.打家劫舍

[案例需求]

[思路分析]

打家劫舍是dp解决的经典问题，动规五部曲分析如下：

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

dp[i] : 考虑下标i(包括i)以内的房屋, 最多可以偷窃的金额为dp[i]

2. 确定递推公式

决定dp[i]的因素是第i房间偷还是不偷 ,

如果偷第i房间, 那么dp[i] = dp[i - 2] + nums[i], 因为dp总是由之前的状态得到现在的状态嘛, 如果要偷i, 那么前一次只能偷i - 2下标的房屋, 用dp[i - 2] + nums[i] 才能得到偷dp[i] 获得的金额
如果不偷第i房间, 那么dp[i] = dp[i - 1], 即包括i - 1房间能够偷到的最大价值
所以, 递推公式就是偷和不偷dp[i]的最大价值: dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);

3. dp数组如何初始化

由递推公式可得出, dp最初是从dp[0]和dp[1]开始初始化的, 因为 dp[2] = Math.max(dp[1], dp[0] + nums[2]);
所以我们需要初始化dp[0]和dp[1], 由题意, dp[0] 意思是偷下标为0的房屋, dp[0] = nums[0]
而, dp[1] 可以选择偷dp[0], 不偷dp[1], 或者是不偷dp[0], 偷dp[1], 所以, dp[1] = Math.max(nums[0], nums[1]);

4. 确定遍历顺序
   dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！

5. 举例推导dp数组
   

[代码实现]

class Solution {
    public int rob(int[] nums) {
        //1. 确定dp[i], 表示下标为i的房屋能够偷到的最大金额dp[i]
        int len = nums.length;
        int[] dp = new int[len];
        //2. 递推公式
        // 偷 dp[i] = dp[i - 2] + nums[i]
        //不偷 dp[i - 1] = dp[i - 1]
        // dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
        

        //3. 初始化
        // dp[0] = nums[0];
        // dp[1] = Math.max(nums[0], nums[1]);
        dp[0] = nums[0];
        if(len > 1)dp[1] = Math.max(nums[0], nums[1]);

        //4. 遍历
        for(int i = 2; i < len; i++){
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[len - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

lt.213. 打家劫舍 II

[案例需求]

[思路分析]

• 其实就是把环拆成两个队列，一个是从0到n-1，另一个是从1到n，然后返回两个结果最大的。
  

[代码实现]

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 1)return nums[0];
        if(len == 2)return Math.max(nums[0], nums[1]);
        return Math.max(
                myRob(Arrays.copyOfRange(nums, 0, len - 1)),
                myRob(Arrays.copyOfRange(nums, 1, len)));
    }

    public int myRob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        if(n > 1)dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

lt.337. 打家劫舍 III

[案例需求]

[思路分析一, 暴力递归]

• 直接从root节点开始往下进行递归,

1. 每一层要么选择root节点, 然后加上root左孩子的左子树上的节点, 并加上root右孩子的右子树上的节点;
2. 要么不选择root节点, 直接从root的左孩子 + root的右孩子节点开始计算。

[代码实现一]

class Solution {
    public int rob(TreeNode root) {
        if(root == null)return 0;
        if(root.left == null && root.right == null)return root.val;

        //偷父节点, val1
        // 那就需要跳过root的直接左右子孩子节点
        int val1 = root.val;
        //把val1 + 后续的递归函数, 这个函数负责计算root的左孩子的左右子树和root的右孩子的子树上的左右节点
        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);

        //不偷父节点, val2
        int val2 = rob(root.left) + rob(root.right);

        return Math.max(val1, val2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路分析二, 记忆化递推

• 所以可以使用一个map把计算过的结果保存一下，这样如果计算过孙子了，那么计算孩子的时候可以复用孙子节点的结果。

思路分析三, 动态规划

1