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


前言

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

今天是跟着代码随想录刷题的第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]);

    }
};


点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部