代码随想录算法训练营第50天|123. 买卖股票的最佳时机 III，188. 买卖股票的最佳时机 IV

123. 买卖股票的最佳时机 III

链接: 参考讲解

class Solution {
    public int maxProfit(int[] prices) {
            int len = prices.length;
            int[][] dp = new int[len][5];

            /**
             * dp[i][0] 无操作
             * dp[i][1] 第一次持有/买入
             * dp[i][2] 第一次卖出
             * dp[i][3] 第二次持有/买入
             * dp[i][4] 第二次卖出
             */

            dp[0][1] = -prices[0];
            dp[0][3] = -prices[0];

            for(int i = 1; i<len; i++){
                dp[i][0] = dp[i-1][0];
                dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
                dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);
                dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);
                dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]);
            }

            return dp[len - 1][4];

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

188. 买卖股票的最佳时机 IV (此题为上一题的进阶版)

链接: 参考讲解

class Solution {
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2*k+1];
        // 初始化
        for(int j = 1; j<2*k; j += 2){
            dp[0][j] = -prices[0];
        }

        for(int i = 1; i < len; i++){
            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[len - 1][2*k];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19