188. 买卖股票的时机 IV

class Solution 
{
public:
    int maxProfit(int k, vector& prices) 
    {

        if (prices.size() == 0) 
        {
            return 0;
        }

        vector> dp(prices.size(), vector(2 * k + 1, 0));

        for (int j = 1; j < 2 * k; j += 2) 
        {
            dp[0][j] = -prices[0];//买入股票
        }

        for (int i = 1; i < prices.size(); i++) 
        {
            for (int j = 0; j < 2 * k - 1; j += 2) 
            {
                dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);//保持原状；买入股票
                dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);//保持原状；卖出股票
            }
        }

        return dp[prices.size() - 1][2 * k];
    }
};

参考：
https://programmercarl.com/0188.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIV.html