【随想录】Day47—第九章 动态规划part09

---

题目1: 198. 打家劫舍

• 题目链接：198. 打家劫舍

---

1- 思路

动规五部曲

• 1. 确定 dp 数组含义
  • dp[i] 代表走到下标 i 能偷的最大金额数，考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
  • 最终需要的结果是 dp[nums.length-1]
• 2. 确定递推公式
  • ① 偷下标 **i** 的情况：此时 dp[i] 考虑 nums[i] + dp[i-2]
    • 此时代表 dp[i] 偷，则前面 i - 2 不能偷
  • **② 不偷下标 **i** 的情况：**此时 dp[i] 考虑 nums[i-1]
  • 结果：dp[i] = Math.max(nums[i] + dp[i-2],dp[i-1])
• 3. dp 数组初始化
  • dp[0] = nums[0] ，此时只有 0 因为是最大值，所以 0 必须偷
  • dp[1] = Math.max(nums[0],nums[1]) ，此时选取二者最大的
• 4. 遍历顺序
  • 由于递推公式可以看出当前 i 是由 i-2 和 i-1 决定的，因此必须从小到大遍历
  • i 从 2 遍历到 nums.size()

---

2- 题解

⭐打家劫舍——题解思路

class Solution {
    public int rob(int[] nums) {

        if(nums==null && nums.length==0) return 0;
        if(nums.length == 1 ) return nums[0];

        // 1. 创建dp数组，即含义
        int[] dp = new int[nums.length];

        // 2. 确定递推公式
        // dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])

        // 3. dp 数组初始化
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);

        // 4. 确定遍历顺序
        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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

题目2: 213. 打家劫舍 II

• 题目链接：213. 打家劫舍 II

---

1- 思路

分情况讨论

• ①情况1：不考虑首尾元素，只考虑 去除首尾 元素的其他部分，这样类似于打家劫舍 1
• ②情况2：不考虑尾元素，只考虑 去除尾元素部分，类似于打家劫舍 1
• ③情况3：不考虑首元素，只考虑 去除首元素部分，类似于打家劫舍 1

---

动规五部曲

• 1. 确定 dp 数组含义
  • dp[i] 代表，当前 i 可以偷的最大的 金额
• 2. 确定递推公式
  • dp[i] = Math.max(nums[i] + dp[i-2],dp[i-1])
• 3. dp 数组初始化
  • ① 不要首位
  • **② 不要末尾位 **
• 4. 遍历顺序
  • 由于递推公式可以看出当前 i 是由 i-2 和 i-1 决定的，因此必须从小到大遍历
  • i 从 2 遍历到 nums.size()

---

2- 题解

⭐打家劫舍 II——题解思路

class Solution {
    public int rob(int[] nums) {
        if(nums==null || nums.length ==0) return 0;
        if(nums.length == 1) return nums[0];
        
        int[] nums1 = new int[nums.length-1];
        int[] nums2 = new int[nums.length-1];
        int index = 0;
        for(int i = 0 ; i <= nums.length-2;i++){
            nums1[index++] = nums[i]; 
        }
        index = 0;
        for(int i = 1 ; i <= nums.length-1;i++){
            nums2[index++] = nums[i]; 
        }

        int res1 = rob1(nums1);
        int res2 = rob1(nums2);

        return Math.max(res1,res2);
    }

    public int rob1(int[] nums){
        if(nums==null || nums.length ==0) return 0;
        if(nums.length == 1) return nums[0];

        // 1.创建 dp 数组
        int[] dp = new int[nums.length];

        // 2.递推公式
        // 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]);

        // 4. 遍历
        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];
    }
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

---

题目3: 打家劫舍 III

• 题目链接：337. 打家劫舍 III

---

1- 思路

思路

• 本题是 树形 dp 的题目，实际上状态转移还是考察对树遍历的熟练度

确定 dp 数组含义

• 定义一维 dp 数组，长度为 2
• 每个树的结点有两个状态
  • 偷 ——> dp[1] ——> 代表偷当前结点，获得的最大金钱
  • 不偷 ——> dp[0] ——> 代表不偷当前结点，获得的最大金钱

递归三部曲（后续遍历二叉树）

• 1. 确定递归参数和返回值
  • **TreeNode root**： 递归函数参数
• 2. 递归函数终止条件
  • 遇到 null 结点，则返回 res
• 3. 递归逻辑
  • 3.1 每层，都定义一个 int[] 长为 2 的数组
  • 3.2 递归 左右节点
  • 3.3 更新当前结点 dp
    • dp[0] 代表不偷当前结点——> dp[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1])
    • dp[1] 代表偷当前结点 ——> dp[1] = root.val + left[0] + right[0];

---

2- 题解

⭐打家劫舍 III——题解思路

class Solution {
    public int rob(TreeNode root) {
        int[] res = Traversal(root);
        return Math.max(res[0],res[1]);

    }

    int[] Traversal(TreeNode root){
        if(root==null){
            return new int[]{0,0};
        }

        // 定义 dp 数组
        int[] dp = new int[2];

        int[] left = Traversal(root.left);
        int[] right = Traversal(root.right);

        // 不偷
        dp[0] = Math.max(left[0],left[1])+ Math.max(right[0],right[1]);
        // 偷 
        dp[1] = root.val + left[0] + right[0];

        return dp;
    }
}
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
26

---