代码随想录训练营Day48

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

提示：这里可以添加本文要记录的大概内容：

今天是跟着代码随想录刷题的第48天，主要学习了买卖股票的最佳时机4，买卖股票冷静期，买卖股票含手续费

提示：以下是本篇文章正文内容，下面案例可供参考

一、买卖股票的最佳时机4

思路：这道题和买卖股票3很像，主要就是找规律，可以买卖k次，用循环来赋值就好了

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
    vector<vector<int>> dp(prices.size(),vector<int>(2*k));
    for(int j=0;j<2*k;j++)
    {
        if(j%2==0) dp[0][j]=-prices[0];
        else dp[0][j]=0;
    }
    for(int i=1;i<prices.size();i++)
    {
        for(int j=0;j<2*k;j++)
        {
            if(j==0)
            {
                dp[i][0]=max(dp[i-1][0],-prices[i]);//今天不持股，保持了昨天也不持或者昨天持股，今天卖了
            }
            if(j!=0&&j%2==0)
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
            }
            if(j%2==1)
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
            }
        }
        
    }
    int max1=INT_MIN;
    for(int j=0;j<2*k;j++)
    {
        max1=max(dp[prices.size()-1][j],max1);
    }
    return max1;

    }
};

二、买卖股票的最佳时机含冷冻期

思路：代码里注释的有，就是要多细分几种情况

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    vector<vector<int>> dp(prices.size(),vector<int>(4));
    //dp[i][0]是第i天不持有股但不是刚卖的，也不在冷冻期最多有多少钱，dp[i][1]是第i天持有股但是不是当天买最多有多少钱，dp[i][2]是第i天在冷冻期最多有多少钱,dp[i][3]是指今天就卖股票最多有多少钱
    dp[0][0]=0;
    dp[0][1]=-prices[0];
    dp[0][2]=0;//考虑第0天，买了又卖就是冷冻期
    dp[0][3]=0;
    for(int i=1;i<prices.size();i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][2]);//今天不持股，不是刚卖的，且不在冷冻期，保持了昨天不在冷冻期，或者昨天在冷冻期
        dp[i][1]=max(max(dp[i-1][1],dp[i][0]-prices[i]),dp[i][2]-prices[i]);//今天持股，保持的昨天持股，或者今天刚买的，但是在非冷冻期才买的
        dp[i][2]=dp[i-1][3];//今天是冷冻期，说明昨天刚卖
        dp[i][3]=dp[i-1][1]+prices[i];//今天卖股票，昨天一定持有股票
        
        
    }
    return max(max(max(dp[prices.size()-1][0],dp[prices.size()-1][1]),dp[prices.size()-1][2]),dp[prices.size()-1][3]);

    }
};

三、买卖股票含手续费

思路：和买卖股票2的代码基本上一样，就是要减去手续费就行了，很简单

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
    vector<vector<int>> dp(prices.size(),vector<int>(2));
    //dp[i][0]是第i天不持有股最多有多少钱，dp[i][1]是第i天持有股最多有多少钱
    dp[0][0]=0;
    dp[0][1]=-prices[0];
    for(int i=1;i<prices.size();i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);//今天不持股，保持了昨天也不持或者昨天持股，今天卖了
        dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);//今天持股，保持的昨天持股，或者今天刚买的，但是这种情况是昨天不持股的价格减去今天购买的价格
    }
    return max(dp[prices.size()-1][0],dp[prices.size()-1][1]);

    }
};