当前位置：网站首页>LeetCode 188. The best time to buy and sell stocks iv*** (double, need triple)

LeetCode 188. The best time to buy and sell stocks iv*** (double, need triple)

2022-07-18 06:36:00 【Evening rain forest bell】

Specific ideas ：

123 Expansion of the topic

Specific code ：

class Solution {
    
public:
    int maxProfit(int k, vector<int>& prices) {
    
        if(k==0||prices.size()==0)
            return 0;
        int inf=-100000;
        int n=prices.size();
        vector<vector<vector<int>>>dp(n,vector<vector<int>>(2,vector<int>(k+1,0)));
        for(int i=1;i<=k;i++){
    
            dp[0][0][i]=dp[0][1][i]=inf;
        }
        dp[0][1][0]=-prices[0];
        for(int i=1;i<n;i++){
    
            dp[i][0][0]=0;
            dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][0][0]-prices[i]);
            for(int j=1;j<=k;j++){
    
                dp[i][0][j]=max(dp[i-1][0][j],dp[i-1][1][j-1]+prices[i]);
                dp[i][1][j]=max(dp[i-1][1][j],dp[i-1][0][j]-prices[i]);
            }
            dp[i][1][k]=inf;
        }
        int ret=0;
        for(int i=0;i<=k;i++){
    
            ret=max(ret,dp[n-1][0][i]);
        }
        return ret;
    }
};
原网站

版权声明
本文为[Evening rain forest bell]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/199/202207151613259286.html

边栏推荐

猜你喜欢

随机推荐