188. 买卖股票的最佳时机 IV

原题链接：188. 买卖股票的最佳时机 IV

 

solution:

        和买卖股票系列3是一样的方法，只不过交易次数为k次。

const int INF = 0x3f3f3f3f;
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if(n == 0) return 0;
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>> (2, vector<int> (k + 1)));
        
        dp[1][1][0] = -prices[0];
        dp[1][0][0] = 0;

        //第一天不可能完成交易
        for(int i = 1;i <= k;i++)
            dp[1][0][i] = -INF;

        // 第一天不可能已经卖出
        for(int i = 1;i <= k;i++)
            dp[1][1][i] = -INF;

        for(int i = 2;i <= n;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 - 1]);
            }

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

            for(int j = 1;j <= k;j++) {
                dp[i][1][j] = max(dp[i - 1][1][j], dp[i - 1][0][j] - prices[i - 1]);
            }
        }

        int res = 0;
        for(int i = 1;i <= k;i++){
            res = max(res,dp[n][0][i]);
        }
        return res;
    }
};