188. Best Time to Buy and Sell Stock IV

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

class Solution {
    int dp[101][1001];
    int solution(int &k, vector<int>& p, int t, int s) {
        if(s == p.size()) return 0;
        if(t == k) return 0;
        if(dp[t][s] != -1) return dp[t][s];
        dp[t][s] = 0;
        int cost = p[s];
        for(int i = s + 1; i < p.size(); i++) {
            dp[t][s] = max(dp[t][s], p[i] - cost + solution(k,p,t + 1, i + 1));
            cost = min(cost, p[i]);
        }
        
        return dp[t][s];
    }
public:
    int maxProfit(int k, vector<int>& p) {
        memset(dp, -1, sizeof(dp));
        return solution(k,p,0,0);
    }
};