leetcode-188-买卖股票的最佳时机IV

class Solution {

public:

    int maxProfit(int k, vector<int>& prices) {

        if (prices.size() < 2 ) return 0;

        k = k> prices.size()/2? prices.size()/2: k;

        vector<int> times(k+1, 0);

        vector<vector<int>> status(2, times);

        vector<vector<vector<int>>> dp(2, status);

        for (int i=0; i<=k; i++) dp[0][1][i] = -prices[0];

        for (int i=1; i<prices.size(); i++){

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

            for (int j=1; j<=k; j++){

                dp[i%2][0][j] = max(dp[(i-1)%2][1][j-1] + prices[i], dp[(i-1)%2][0][j]);

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

            }

        }

        auto res = max_element(begin(dp[(prices.size()-1)%2][0]), end(dp[(prices.size()-1)%2][0]));

        return *res;

    }

};