[C++知识库] C++打家劫舍系列最清晰简洁代码

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> C++打家劫舍系列最清晰简洁代码 -> 正文阅读

[C++知识库]C++打家劫舍系列最清晰简洁代码

在这里插入图片描述
可以构建动态规划方程： dp[i]=max(dp[i-2]+nums[i],dp[i-1])即分为抢了和没抢两个情况计算最大值

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

在这里插入图片描述

这里加了一个首尾不能同时选择的限制，等于说可以分为选首位和选尾位两种情况，分开讨论即可。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1)return nums[0];
        if(n==2)return max(nums[0],nums[1]);
        vector<int>dpa(n+1);
        dpa[0]=nums[0],dpa[1]=max(nums[0],nums[1]);
        for(int i=2;i<n-1;i++){
            dpa[i]=max(dpa[i-2]+nums[i],dpa[i-1]);
        }
        vector<int>dpb(n+1);
        dpb[0]=nums[1],dpb[1]=max(nums[1],nums[2]);
        for(int i=2;i<n-1;i++){
            dpb[i]=max(dpb[i-2]+nums[i+1],dpb[i-1]);
        }
        return max(dpa[n-2],dpb[n-2]);
    }
};

当时写的时候还tm犯了个sb错误，把dpb的方程里的dpb写成了dpa然后一直报错然后不知道原因，tmd真眼瞎。

在这里插入图片描述
这玩意咋一看我都懵了，然鹅它可以转化成打家劫舍问题，就是把数组换一遍。

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int n=nums.size();
        if(n==1)return nums[0];
        //if(n==2)return max(nums[0],nums[1]);
        int Maxval=0;
        for(int val:nums){
            Maxval=max(Maxval,val);
        }
        vector<int>sum(Maxval+1);
        for(int val:nums){
            sum[val]+=val;//重点就是一个转化
        }
        vector<int>dp(Maxval+1);
        dp[0]=sum[0],dp[1]=max(sum[0],sum[1]);
        for(int i=2;i<=Maxval;i++){
            dp[i]=max(dp[i-2]+sum[i],dp[i-1]);
        }
        return dp[Maxval];
    }
};