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

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解法

和123. 买卖股票的最佳时机III一样的思路。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
    if (prices.empty()) return 0;
    if(k>=prices.size()) return quickSolution(prices);

    vector<int> dp(k+1, 0);
    vector<int> minCost(k+1, prices[0]);

    for (int i=1;i<prices.size();i++){
        for(int k=1;k<minCost.size();k++){
            minCost[k]=min(minCost[k], prices[i]- dp[k-1]);
            dp[k]=max(dp[k],prices[i]-minCost[k]);
        }
    }  

    return dp[k];
    }

    int quickSolution(vector<int>& prices){
        int profit=0;
        for(int i=1;i<prices.size();i++){
            if(prices[i]>prices[i-1]){
                profit+=prices[i]-prices[i-1];
            }
        }
        return profit;
    }
};