DP刷题练习（三）

文章内容学习自代码随想录，感谢carl！！！！

[TOC]

198. 打家劫舍 - 力扣（LeetCode）

int rob(vector<int>& nums) {
   
        int n=nums.size();
        if(n==0) return 0;
        if(n==1) return nums[0];
        int dp[n+1];//考虑下标i(包含)，前i个房间所能偷盗最大金币为dp[i]
        dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<n;i++)
        {
   
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }       
        return dp[n-1];
    }
//对于当前的房间都有不偷和偷两种状态
//不偷是dp[i]=dp[i-1]
//偷是dp[i]=dp[i-2]+nums[i]

213. 打家劫舍 II - 力扣（LeetCode）

打家劫舍二与一的区别在于，头尾是连成环的，就是说头尾是相邻的，针对头尾，我们有三种情况

①头尾都不偷

②头偷尾不偷

③头不偷尾偷

其实又可以发现我们可以将①包含于②③中，我们考虑0---n-2与1---n-1，并没有说我们一定要偷0，或一定要偷n-1，只是不考虑两者同时出现的情况所以我们只要用俩个dp数组分别考虑0---n-2与1---n-1,取其最大值便是结果，其余都与上题一致

int rob(vector<int>& nums) {
   
        int n=nums.size();
        if(n==0) return 0;
        else if(n==1) return nums[0];
        else if(n==2) return max(nums[0],nums[1]);
        int dp1[n-1],dp2[n-1];//定义两个长度为n-1的数组即可
        //对于dp1，其考虑，不包涵最后一个元素的情况
        dp1[0]=nums[0],dp1[1]=max(nums[0],nums[1]);
        for(int i=2;i<n-1;i++) dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i]);

        //构建一个nums2数组服务于dp2，dp2考虑不包含第一个元素的情况
        int nums2[n-1];
        for(int i=0;i<n-1;i++) nums2[i]=nums[i+1];
        dp2[0]=nums2[0],dp2[1]=max(nums2[0],nums2[1]);
        for(int i=2;i<n-1;i++) dp2[i]=max(dp2[i-1],dp2[i-2]+nums2[i]);

        return max(dp1[n-2],dp2[n-2]);
    }

337. 打家劫舍 III - 力扣（LeetCode）

树形dp入门

我们设置状态dp【0】为不偷当前节点所能获得的最大值，dp【1】为偷当前节点所能获得的最大值

我们采用后序遍历，从下往上遍历，最后看偷根结点，不偷根结点，所能获得的最大值是什么

//偷当前节点：int val1=cur->val+leftdp[0]+rightdp[0];
//当前节点若偷，则其左右儿子不能偷

//不偷当前节点：int val2=max(leftdp[0],leftdp[1])+max(rightdp[0],rightdp[1]);
//当前节点若不偷，则其左右各取所获最大价值

vector<int> robtree(TreeNode *cur)
    {
   
        if(cur==NULL) return vector<int> {
   0,0};
        vector<int> leftdp=robtree(cur->left);
        vector<int> rightdp=robtree(cur->right);
        //偷当前节点
        int val1=cur->val+leftdp[0]+rightdp[0];
        //不偷当前节点
        int val2=max(leftdp[0],leftdp[1])+max(rightdp[0],rightdp[1]);
        return vector<int> {
   val2,val1};
    }
    int rob(TreeNode* root) {
   
        vector<int> result=robtree(root);
        return max(result[0],result[1]);
    }

121. 买卖股票的最佳时机 - 力扣（LeetCode）

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。

就是你的买卖都只能有一次

dp含义如代码所示

dp[i][0]=max(dp[i-1][0],-prices[i]);
//第i天持有股，你可能是之前一天就持有，或者是今天买入才持有，说到底是找最小的价格买入

 dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]);
//第i天不持有股，你可以是前一天就不持有了，也可以是前一天就持有了，但是今天卖出

初始化：

dp[0][0]=-prices[0]; //第0天持股，那你第0天肯定要买入！
dp[0][1]=0;          //第0天不持股

int maxProfit(vector<int>& prices) {
   
        int n=prices.size();
        int dp[n][2];//dp[i][0]表示第i天持有股票的所获得的最大利润
                     //dp[i][1]表示第i天不持有股票所获得的最大利润
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for(int i=1;i<n;i++){
   
            dp[i][0]=max(dp[i-1][0],-prices[i]);
            dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]);
        }
        return dp[n-1][1];
    }

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

本题与上题的区别是股票可以买卖多次，所以你买入股票时你当前拥有的金额可以不是0，所以在此处持股的最大利润如下

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

本题有个坑点就是题目说股票可以同一天买入然后卖出

但是题目说了你最多只能持有一支股票，所以你今天要买入，必然前一天不持股所以是dp【i-1]】【1】-prices【i】

然后今天又卖出所以是dp【i-1]】【1】-prices【i】+prices【i】<==> dp【i-1】【1】

   int maxProfit(vector<int>& prices) {
   
        int n=prices.size();
        int dp[n][2];//dp[i][0]表示第i天持有股票的所获得的最大利润
                     //dp[i][1]表示第i天不持有股票所获得的最大利润
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for(int i=1;i<n;i++){
   
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[n-1][1];
    }

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

int maxProfit(vector<int>& prices) {
   
        int n=prices.size();
        int dp[n][5];//dp[i][0]表示不操作
                     //dp[i][1]表示第一次持有
                     //dp[i][2]表示第一次不持有
                     //dp[i][3]表示第二次持有
                     //dp[i][4]表示第二次不持有
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        dp[0][2]=0;
        dp[0][3]=-prices[0];
        dp[0][4]=0;
        for(int i=1;i<n;i++){
   
            dp[i][1]=max(dp[i-1][1],-prices[i]);
            dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]);
            dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]);
            dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]);
        }
        return dp[n-1][4];
    }

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

由上一题两次的情况可以推广到k次的情况

    int maxProfit(int k, vector<int>& prices) {
   
        int n=prices.size();
        int dp[n][2*k+1];
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=2*k;i++)
        {
   
            if(i%2==0) dp[0][i]=0;
            else dp[0][i]=-prices[0];
        }
        for(int i=1;i<n;i++)
        {
   
            for(int j=1;j<=2*k;j++)
            {
   
                if(j%2==0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
                else if(j%2!=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
            }
        }
        return dp[n-1][2*k];
    }

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

由于具有冷冻期所以我们要明确

到底是拿一天卖出了股票所以我们把不持有股票的状态进行了拆分

int maxProfit(vector<int>& prices) {
   
        int n=prices.size();
        int dp[n][4];//dp[i][0]表示第i天持有股票
                     //dp[i][1]表示第i天保持卖出股票状态
                     //dp[i][2]表示第i天卖出股票
                     //dp[i][3]表示第i天是冷冻期
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        dp[0][2]=0;
        dp[0][3]=0;
        for(int i=1;i<n;i++)
        {
   
            dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));
            dp[i][1]=max(dp[i-1][1],dp[i-1][3]);
            dp[i][2]=dp[i-1][0]+prices[i];
            dp[i][3]=dp[i-1][2];
        }
        return max(dp[n-1][3],max(dp[n-1][2],dp[n-1][1]));
    }