跳至主要內容

买卖股票IV——三维DP到二维压缩的完整推导

老张2026/4/30大约 7 分钟

买卖股票IV——三维DP到二维压缩的完整推导

适读人群：Java后端工程师、股票DP进阶学习者 | 阅读时长：约22分钟 | 难度：Hard

开篇故事

买卖股票IV（LeetCode 188）是股票系列的"终极Boss"。它问的是：最多完成 k 笔交易能获得的最大利润是多少？

k 是一个变量，这意味着之前那种"2个状态变量（cash/hold）"的简单框架不够用了，必须增加一个维度来跟踪"已完成的交易次数"。

我第一次做这道题，写出了一个三维DP，思路是对的，但时间和空间都是 O(n×k)，在k极大时会超时。后来才学会了一个剪枝技巧：当 k >= n/2 时，可以当作无限次买卖（因为一次有意义的买卖至少需要2天，n天最多完成 n/2 次有意义的交易）。

这道题还有个很有意思的维度压缩：三维数组 dp[i][j][0/1] 可以在遍历时，用"以k为外层的二维滚动"压缩，让空间降到 O(k)。

整个推导过程很有意思，我们一步步来。

一、题目解析

题号：LeetCode 188. Best Time to Buy and Sell Stock IV

题目描述：给你一个整数数组 prices 和一个整数 k，其中 prices[i] 是某只股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例：

  • 输入：k = 2，prices = [2,4,1]，输出：2
  • 输入：k = 2，prices = [3,2,6,5,0,3]，输出：7（2→6，0→3）

二、DP思路推导

2.1 三维状态定义

在714的基础上，增加一个维度 j 来记录已完成的交易次数。

定义 dp[i][j][s]：

  • i：天数（0到n-1）
  • j：已完成的交易次数（0到k）
  • s：当前持仓状态（0=不持有，1=持有）

dp[i][j][0] = 第 i 天结束，已完成 j 次交易，不持有股票的最大收益

dp[i][j][1] = 第 i 天结束，已完成 j 次交易，持有股票的最大收益

约定：一次"完整交易"=买入+卖出，在卖出时计数（也可以约定在买入时计数，两种都对，要一致）。

2.2 状态转移方程

不持有状态 dp[i][j][0]：

  • 昨天也不持有，今天不操作：dp[i-1][j][0]
  • 昨天持有，今天卖出（完成一次交易，j从j-1变为j）：dp[i-1][j-1][1] + prices[i]
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1] + prices[i])

持有状态 dp[i][j][1]：

  • 昨天也持有，今天不操作：dp[i-1][j][1]
  • 昨天不持有，今天买入（不完成新交易，j不变）：dp[i-1][j][0] - prices[i]
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0] - prices[i])

2.3 边界条件

  • dp[i][0][0] = 0：完成0次交易，不持有，收益为0
  • dp[i][0][1] = -∞：完成0次交易还持有股票，不合法（设为最小值）
  • dp[0][j][0] = 0：第0天不持有，收益为0
  • dp[0][j][1] = -prices[0]（j >= 1）：第0天买入，此时 j 应为0（还没卖出），实际上在买入时 j 不变，只有卖出才增加 j

这里的边界条件很容易搞混，建议直接初始化：

// 所有状态初始化为-∞（不可达）
for (int j = 0; j <= k; j++) {
    Arrays.fill(dp[0][j], Integer.MIN_VALUE / 2);
}
// 第0天不持有任何次数交易都是0（没有操作）
for (int j = 0; j <= k; j++) dp[0][j][0] = 0;
// 第0天持有（买入），交易次数为0（还没卖出）
dp[0][0][1] = -prices[0];

2.4 剪枝：k >= n/2 时退化为无限次

如果 k >= n/2，一天买一天卖的次数上限已经满足，可以当成无限次（122题）处理，避免 k 超大时的超时。

if (k >= n / 2) {
    return maxProfitInfinite(prices);  // 贪心或122的DP
}

三、解法一：三维DP

public class BestTimeBuySellIV {
    
    /**
     * 188. 买卖股票IV - 三维DP
     * 时间复杂度：O(n * k)
     * 空间复杂度：O(n * k)
     */
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0 || k == 0) return 0;
        
        // 剪枝：k >= n/2 时等同于无限次
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                profit += Math.max(0, prices[i] - prices[i - 1]);
            }
            return profit;
        }
        
        // dp[i][j][0/1]: 第i天，完成j次交易，不持有/持有的最大收益
        int[][][] dp = new int[n][k + 1][2];
        
        // 初始化：不可达状态设为极小值
        for (int[][] d : dp) {
            for (int[] dd : d) Arrays.fill(dd, Integer.MIN_VALUE / 2);
        }
        
        // 第0天的初始状态
        for (int j = 0; j <= k; j++) dp[0][j][0] = 0;
        dp[0][0][1] = -prices[0];  // 第0天买入，完成0次（还没卖）
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                // 不持有：不动 or 今天卖出（完成第j次交易）
                dp[i][j][0] = dp[i - 1][j][0];
                if (j > 0 && dp[i - 1][j - 1][1] != Integer.MIN_VALUE / 2) {
                    dp[i][j][0] = Math.max(dp[i][j][0], dp[i - 1][j - 1][1] + prices[i]);
                }
                // 持有：不动 or 今天买入（交易次数不变）
                dp[i][j][1] = dp[i - 1][j][1];
                if (dp[i - 1][j][0] != Integer.MIN_VALUE / 2) {
                    dp[i][j][1] = Math.max(dp[i][j][1], dp[i - 1][j][0] - prices[i]);
                }
            }
        }
        
        // 最大收益：最后一天，完成0到k次交易，不持有状态
        int ans = 0;
        for (int j = 0; j <= k; j++) {
            ans = Math.max(ans, dp[n - 1][j][0]);
        }
        return ans;
    }
}

四、解法二：二维压缩（消除天数维度）

由于 dp[i] 只依赖 dp[i-1]，可以消除天数维度，用两个二维数组（或两行）滚动更新：

/**
 * 188. 买卖股票IV - 二维DP（压缩天数维度）
 * 时间复杂度：O(n * k)
 * 空间复杂度：O(k)
 */
public int maxProfitOptimized(int k, int[] prices) {
    int n = prices.length;
    if (n == 0 || k == 0) return 0;
    
    if (k >= n / 2) {
        int profit = 0;
        for (int i = 1; i < n; i++) profit += Math.max(0, prices[i] - prices[i - 1]);
        return profit;
    }
    
    // dp[j][0] = 完成j次交易，不持有的最大收益
    // dp[j][1] = 完成j次交易，持有的最大收益
    int[][] dp = new int[k + 1][2];
    for (int[] d : dp) Arrays.fill(d, Integer.MIN_VALUE / 2);
    
    // 初始化第0天
    for (int j = 0; j <= k; j++) dp[j][0] = 0;
    dp[0][1] = -prices[0];
    
    for (int i = 1; i < n; i++) {
        // 注意：j从大到小，防止本轮的dp[j-1]影响dp[j]
        for (int j = k; j >= 0; j--) {
            // 不持有：不动 or 卖出（从j-1次完成变为j次）
            int notHold = dp[j][0];
            if (j > 0 && dp[j - 1][1] != Integer.MIN_VALUE / 2) {
                notHold = Math.max(notHold, dp[j - 1][1] + prices[i]);
            }
            // 持有：不动 or 买入（次数不变）
            int hold = dp[j][1];
            if (dp[j][0] != Integer.MIN_VALUE / 2) {
                hold = Math.max(hold, dp[j][0] - prices[i]);
            }
            dp[j][0] = notHold;
            dp[j][1] = hold;
        }
    }
    
    int ans = 0;
    for (int j = 0; j <= k; j++) ans = Math.max(ans, dp[j][0]);
    return ans;
}

状态转移的Mermaid图：

五、举一反三

股票系列对比：

题号描述k值
121最多1次k=1
122无限次k=∞
123最多2次k=2
188最多k次变量k
309冷冻期k=∞，多状态
714手续费k=∞，多代价

123（k=2）是188的特例，可以直接展开188的k=2情况来解。

六、踩坑实录

坑一：交易次数在买入时计还是卖出时计

选其中一种，保持一致。本文选卖出时计（卖出后j+1），这样 dp[i][j][0] 中的 j 是"完成了 j 次完整交易后不持有"。如果选买入时计，边界条件和转移方程需要相应调整。

坑二：忘记剪枝 k >= n/2

当 k 非常大（比如 k = 10^9）时，三维DP会爆内存和超时。必须加 k >= n/2 的判断，转为无限次交易问题（贪心或122的DP）。

坑三：不可达状态的初始值

如果把不可达状态初始化为0，可能被错误地当作合法状态继续传递。要初始化为极小值（Integer.MIN_VALUE / 2，注意除2防止+prices溢出变成正数）。

坑四：二维压缩时的遍历方向

二维压缩（消除天数维度）时，j 要从大到小遍历，原因类似01背包倒序：卖出操作用到了 dp[j-1][1]（前一个次数的持有状态），如果正序，dp[j-1] 可能已经被本轮更新过。

七、总结

买卖股票IV是股票系列的最终形态：

  1. 三维DP：清晰但空间大
  2. 二维压缩：消除天数维度，空间降到O(k)
  3. 剪枝技巧：k >= n/2 时退化为无限次问题

股票系列所有题都基于同一个状态机框架（持有/不持有），加上交易次数维度后，就是188的完整解。

编辑此页
最近更新:
贡献者: xiaozhangge