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

代码

class Solution {
    public int maxProfit(int k, int[] prices) {
        int size = prices.length;
        if(size == 0) return 0;
        //多了一个0状态
        int jLen = 2 * k + 1;
        int [][] dp = new int[size][jLen];
        //奇数次数买入，偶数次数卖出
        for(int j = 1; j < 2 * k ; j +=2 ){
            dp[0][j] = -prices[0];
        }
        for(int i = 1 ; i < size; i++ ) {
            //2 * k - 1 + 2 = 2 * k + 1 = jLen
            for( int j = 0; j < 2 * k -1; j += 2) {
                //奇数
                 dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
                 dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[size - 1][2 * k ];
    }
}