当前位置：首页 > article >正文

198.213.337.打家劫舍

article 2025/1/4 5:28:23

198.213.337.打家劫舍

198.打家劫舍

思路：动态规划，有点类似122.股票II

dp[i] [0]表示第i个房间为止偷到的最大金额且第i天没偷

dp[i] [0]表示第i个房间为止偷到的最大金额且第i天偷了

初始化dp[0] [0]=0, dp[0] [1]=nums[0]

从第二间屋开始遍历,金额有两种情况：

1.今天偷：昨天一定没偷 dp[i-1][0]+nums[i]

2.今天不偷：两种情况取最大值

（1）昨天偷了：dp[i-1][1]

（2）昨天也没偷：dp[i-1][0]

dp[i][0]=max(dp[i-1][1],dp[i-1][0]);

代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>>dp (n,vector<int>(2));
        dp[0][0]=0;
        dp[0][1]=nums[0];
        for(int i=1;i<n;i++){
            //今天不偷
            dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
            //今天偷
            dp[i][1]=dp[i-1][0]+nums[i];
        }
        return max(dp[n-1][1],dp[n-1][0]);
    }
};

213.打家劫舍II

思路：动态规划

对于198题多了一个圈的限制，即初始化的时候做限制，从第二间屋开始动态规划：

（1）选了dp[1][0]第一天没偷做开头，

那么最后一天偷不偷都可，取max(dp[n-1][1],dp[n-1][0])

初始条件：第二天偷or不偷都可以， dp2[1][0]=0 dp2[1][1]=nums[1]

（2）选了dp[1][1]第一天偷了做开头

那么最后一天一定没偷，只能取dp[n-1][0]

初始条件：第二天一定没偷， dp[1][0]=nums[0] dp[1][1]=nums[0]

再看情况1，2哪个更大

另注意：环形偷窃要注意越界，只有一个房子直接return

代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>>dp (n,vector<int>(2));
        vector<vector<int>>dp2 (n,vector<int>(2));
        int a=0;
        int b=0;
        //环形偷窃要注意越界，只有一个房子直接return
        if(n==1)
        return nums[0];
        //第一天偷,第二天不偷
        dp[1][0]=nums[0];
        dp[1][1]=nums[0];
        for(int i=2;i<n;i++){
            //今天不偷
            dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
            //今天偷
            dp[i][1]=dp[i-1][0]+nums[i];
        }
        a=dp[n-1][0];//第一天偷 最后一天只能不偷
        //第一天不偷,第二天偷or不偷
        dp2[1][0]=0;
        dp2[1][1]=nums[1];
        for(int i=2;i<n;i++){
            //今天不偷
            dp2[i][0]=max(dp2[i-1][1],dp2[i-1][0]);
            //今天偷
            dp2[i][1]=dp2[i-1][0]+nums[i];
        }
        b=max(dp2[n-1][1],dp2[n-1][0]);
        return max(a,b);
    }
};

337.打家劫舍III

思路：二叉树递归+动态规划

对于当前结点node有两种情况：

（1）node偷：左右孩子一定不偷

（2）node不偷：左偷 or 不偷最大值+右偷 or 不偷最大值

最终返回根结点root 偷 or 不偷最大值

使用一个vector<int> dp实际上每次只使用size为2的vector，递归时返回当前结点{不偷，偷}能得到的最大和

代码：

class Solution {
public:        
    int rob(TreeNode* root) {
        vector<int>dp=dfs(root);
        return max(dp[0],dp[1]);
    }
    vector<int> dfs(TreeNode* root){
        if(root==nullptr)
        return {0,0};
        //[0]是不偷，[1]是偷
        vector<int> left=dfs(root->left);
        vector<int> right=dfs(root->right);
        //当前root偷，左右孩子不偷最大值的和
        int tou=left[0]+right[0]+root->val;
        //当前root不偷，左右孩子偷or不偷最大值的和
        int butou=max(left[1],left[0])+max(right[1],right[0]);
        return {butou,tou};
    }
};