188. the best time to buy and sell stocks IV

Original link ：188. The best time to buy and sell stocks IV

 

solution:

        And trading stock series 3 It's the same way , Only the number of transactions is k Time .

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;

        // It is impossible to complete the transaction on the first day 
        for(int i = 1;i <= k;i++)
            dp[1][0][i] = -INF;

        //  It can't have been sold on the first day 
        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;
    }
};