算法训练营day43 | {188.买卖股票的最佳时机IV, 309.买卖股票的最佳时机含冷冻期, 714.买卖股票的最佳时机含手续费}

第九章动态规划part09，股票问题进阶。

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

1.1 解题分析

至多有2次交易时，一天可以拆解成如下5个状态：

  • 0： 不操作
  • 1： 第一次持有
  • 2： 第一次不持有
  • 3： 第二次持有
  • 4： 第二次不持有

本题要求至多有k次交易，那么同样可以拆解成 2k + 1 次交易，并且可以发现，除了0以外，偶数就是卖出，奇数就是买入。

DP五部曲：

  1. dp数组定义：
    • dp[i][j] i表示第i天 j表示状态[0-2k]，dp[i][j]表示第i天状态j所剩最大现金。
  2. 递推公式：
    • dp[i][0] = dp[i - 1][0] 不操作，延续前一天的状态
    • dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]) 其实第一个状态没有必要设置，第一次持有之前手里的现金就是0。
    • dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
    • dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
    • dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])
    • … (关键就是把第二个维度抽象成用j表达。)
  3. dp数组初始化：
    • dp[0][0] = 0
    • dp[0][1] = -prices[0]
    • dp[0][2] = 0
    • dp[0][3] = -prices[0]
    • dp[0][4] = 0
    • … (同样第二个维度做一个抽象，j是奇数时，d[0][j] = -prices[0])
  4. 遍历顺序：从前往后
  5. 打印dp数组。

1.2 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2 * k + 1];
        for (int j = 1; j < 2 * k; j += 2) dp[0][j] = - prices[0];
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 2 * k; 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[n - 1][2 * k];
    }
}

309. 买卖股票的最佳时机含冷冻期

2.1 解题分析

将原来的“不持有”拆成卖出、保持卖出两个状态，是为了明确冷冻期一定是卖出的后一天递推来的，买卖过程中的状态可以拆解成如下4个状态：

  • 0：持股
  • 1：保持卖出股票
  • 2：卖出股票
  • 3：冷冻期

DP五部曲：

  1. dp数组定义：
    • dp[i][j] i表示第i天 j表示状态[0-3]，dp[i][j]表示第i天状态j所剩最大现金。
  2. 递推公式：
    • dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i])
    • dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])
    • dp[i][2] = dp[i - 1][0] + prices[i]
    • dp[i][3] = dp[i - 1][2]
  3. dp数组初始化：
    • dp[0][0] = -prices[0]
    • dp[0][1] = 0 (本身不合理，看递推公式需要初始化成什么值)
    • dp[0][2] = 0
    • dp[0][3] = 0
  4. 遍历顺序：从前往后
  5. 打印dp数组。

依据示例分析题目状态

2.2 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][4];
        dp[0][0] = - prices[0];

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

714.买卖股票的最佳时机含手续费

3.1 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[n - 1][1];
    }
}

4. 今日收获

  • 从买卖一次到买卖多次，从最多买卖两次到最多买卖k次，从冷冻期到手续费，股票系列关键就是拆解清楚买卖过程中的状态，递推还是比较简单的。
  • 2月初放假了，还有6天内容要补，OMG。。。
  • 学习时长：4小时
Leetcode > 动态规划
#Java #代码随想录
算法训练营day43 | {188.买卖股票的最佳时机IV, 309.买卖股票的最佳时机含冷冻期, 714.买卖股票的最佳时机含手续费}
http://paopaotangzu.xyz/cn/day43_leetcode/
作者
PROTON TANG
发布于
2026年1月31日
许可协议