动态规划---打家劫舍问题

代码随想录训练营day48 动态规划模块 打家劫舍问题

1.leetcode198.打家劫舍

力扣题目链接

1.1思路

  这题对于我来说比较不好想的就是递推公式，假如现在准备考虑偷第i家，那么偷了i-1家的时候，就不能偷第i家了，所以此时dp[i]=dp[i-1];如果没有偷第i-1家，那么需要得到最大金额的话，i-2家肯定被偷了，此时dp[i-2]+nums[i]。

1.2做题步骤及详细代码

  按照动态规划的做题步骤来分析

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

dp[i]表示前面有索引i的时候所能偷到的最多金额

   2. 确定递推公式

根据下面得出递推公式dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i])**

  3. dp数组的初始化问题

因为整体是由0和1推导出来的所以都要初始化,dp[0]=nums[0],dp[1]=Math.max(nums[0],nums[1])

  4.确定遍历顺序

从前往后的遍历

  5.推导dp数组

代码示例

class Solution {
    public int rob(int[] nums) {
    int[] dp=new int[nums.length];
    dp[0]=nums[0];
    if(nums.length==1) return 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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2.leetcode213.打家劫舍Ⅱ

力扣题目链接

2.1思路

这题思路跟第一题差不多，不一样的就是需要分情况讨论

1. 当不偷第一个的情况
2. 不偷最后一个的情况

2.2做题步骤及详细代码

做题步骤跟上面基本一样

   但是这题需要注意的是数组长度只有2时候，就直接返回两种情况的第一个索引。

代码示例

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

3.leetcode337.打家劫舍Ⅲ

力扣题目链接

3.1思路

   思路还是跟上面差不多，这难点就是二叉树的递归遍历，可以定义一个res数组，长度为2，记录root位置偷与不偷，然后在定义做左边和右边的数组，当root位置不偷的时候，考虑左边和右边分别偷不偷，这种情况左边和右边不干预。

   //res[0]表示不偷，此时左边max(偷，不偷)+右边max(偷，不偷)
   //res[1]表示偷遍历位置的父节点，等于左边不偷，右边不偷，加上父节点的值
   res[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
   res[1]=left[0]+right[0]+root.val;

3.2做题步骤及详细代码

代码示例

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
       int[] res=sb(root);
       return Math.max(res[0],res[1]);
    }
    public int[] sb(TreeNode root){
        int[] res=new int[2];
        if(root==null){
            return res;
        }

        int[] left=sb(root.left);
        int [] right=sb(root.right);
        //res[0]表示不偷，此时左边max(偷，不偷)+右边max(偷，不偷)
        //res[1]表示偷遍历位置的父节点，等于左边不偷，右边不偷，加上父节点的值
        res[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        res[1]=left[0]+right[0]+root.val;

        return res;
    }
}
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