当你面对LeetCode上的六道股票买卖问题时，第一反应可能是：每道题都要单独学一种解法？这正是无数开发者的误区。实际上，这六道题可以用同一套状态转移方程统一解决——区别只在于边界条件的细微差异。

股票买卖问题系列是动态规划中"状态机DP"的教科书级案例。它的核心思想是将问题抽象为有限状态的转换：每一天，你只有两种可能的状态——持有股票或不持有股票。而在这两种状态之间转换的动作只有三种：买入、卖出、或什么都不做。这个简洁的状态模型，能够覆盖从单次交易到无限次交易、从冷冻期到手续费的所有变体。

一个框架，六道题目

先看这六道题的约束差异：

题目 难度 交易次数限制 额外约束
121. 买卖股票的最佳时机 简单 最多1次 无
122. 买卖股票的最佳时机 II 简单 无限次 无
123. 买卖股票的最佳时机 III 困难 最多2次 无
188. 买卖股票的最佳时机 IV 困难 最多k次 无
309. 买卖股票的最佳时机含冷冻期 中等 无限次 卖出后隔一天才能买
714. 买卖股票的最佳时机含手续费 中等 无限次 每次交易收取fee

看似差异巨大，但它们共享同一个状态定义：dp[i][k][0/1] 表示第i天结束时，最多允许进行k次交易，当前不持有/持有股票时的最大利润。

状态转移的核心方程

状态机的精髓在于明确每个状态可以转换到哪些状态。对于股票问题，状态转移图如下：

     买入           卖出
  ┌─────────→ 持有 ─────────→
  │            (1)            │
未持有                         未持有
  (0)                          (0)
  │                            ↑
  └────── rest ──── rest ──────┘

基于这个状态图，通用状态转移方程为：

$$dp[i][k][0] = \max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])$$$$dp[i][k][1] = \max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])$$

第一个方程的含义：今天不持有股票，要么昨天就不持有（rest），要么昨天持有今天卖出（sell）。第二个方程的含义：今天持有股票，要么昨天就持有（rest），要么昨天不持有今天买入（buy）——注意买入会消耗一次交易额度，所以是从 k-1 转移过来。

边界条件是整个框架的基石：

  • $dp[-1][k][0] = 0$：还没开始时，利润为0
  • $dp[-1][k][1] = -\infty$：还没开始时不可能持有股票
  • $dp[i][0][0] = 0$：不允许交易时，利润为0
  • $dp[i][0][1] = -\infty$：不允许交易时不可能持有股票

LeetCode 121：只允许一次交易

当 k = 1 时，状态维度可以简化。因为 k 始终为1，不再需要跟踪交易次数：

$$dp[i][0] = \max(dp[i-1][0], dp[i-1][1] + prices[i])$$$$dp[i][1] = \max(dp[i-1][1], -prices[i])$$
public int maxProfit(int[] prices) {
    int n = prices.length;
    // dp[i][0] = 第i天不持有股票的最大利润
    // dp[i][1] = 第i天持有股票的最大利润
    int[][] dp = new int[n][2];
    dp[0][0] = 0;
    dp[0][1] = -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], -prices[i]);
    }
    return dp[n-1][0];
}

空间优化版本——只保留前一个状态：

public int maxProfit(int[] prices) {
    int dp0 = 0;           // 不持有股票
    int dp1 = Integer.MIN_VALUE;  // 持有股票
    
    for (int price : prices) {
        dp0 = Math.max(dp0, dp1 + price);
        dp1 = Math.max(dp1, -price);
    }
    return dp0;
}

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

这道题还有一个直观的贪心解法：遍历数组，维护最小买入价格和最大利润：

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;
    
    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }
    return maxProfit;
}

LeetCode 122：无限次交易

当交易次数无限制时，k 和 k-1 等价，状态方程简化为：

$$dp[i][0] = \max(dp[i-1][0], dp[i-1][1] + prices[i])$$$$dp[i][1] = \max(dp[i-1][1], dp[i-1][0] - prices[i])$$
public int maxProfit(int[] prices) {
    int dp0 = 0;
    int dp1 = Integer.MIN_VALUE;
    
    for (int price : prices) {
        int temp = dp0;
        dp0 = Math.max(dp0, dp1 + price);
        dp1 = Math.max(dp1, temp - price);
    }
    return dp0;
}

注意这里需要用 temp 保存旧的 dp0，因为计算 dp1 时需要用到更新前的 dp0。

这道题有一个更优雅的贪心解法：只要价格上涨就卖出。为什么这个策略正确？因为任何上涨区间，都可以分解为若干个相邻上涨：

价格序列: 1, 2, 3, 4, 5
贪心策略: (2-1) + (3-2) + (4-3) + (5-4) = 4
一次买卖: 5 - 1 = 4

两者结果相同，但贪心策略将一次大交易拆成了多次小交易，在无限次交易的条件下完全等价。

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i-1]) {
            profit += prices[i] - prices[i-1];
        }
    }
    return profit;
}

贪心算法的正确性可以用数学归纳法证明：假设最优解在某天持有了股票而没有卖出，而第二天价格上涨。那么在这两天之间卖出再买入，不会减少总利润，但符合贪心策略。通过不断交换，任何最优解都可以转化为贪心解的形式。

LeetCode 123：最多两次交易

k = 2 时，必须完整保留状态维度。但 k 很小，可以直接展开：

public int maxProfit(int[] prices) {
    // 四个状态：第一次买入后、第一次卖出后、第二次买入后、第二次卖出后
    int buy1 = Integer.MIN_VALUE;
    int sell1 = 0;
    int buy2 = Integer.MIN_VALUE;
    int sell2 = 0;
    
    for (int price : prices) {
        // 注意更新顺序：从后往前，避免状态污染
        sell2 = Math.max(sell2, buy2 + price);
        buy2 = Math.max(buy2, sell1 - price);
        sell1 = Math.max(sell1, buy1 + price);
        buy1 = Math.max(buy1, -price);
    }
    return sell2;
}

理解这四个状态的关键是：它们代表的是在第i天结束时处于该状态的最大利润。buy1 表示已完成第一次买入（持有第一支股票），sell1 表示已完成第一次卖出，以此类推。

状态转移方程为：

$$buy1[i] = \max(buy1[i-1], -prices[i])$$$$sell1[i] = \max(sell1[i-1], buy1[i-1] + prices[i])$$$$buy2[i] = \max(buy2[i-1], sell1[i-1] - prices[i])$$$$sell2[i] = \max(sell2[i-1], buy2[i-1] + prices[i])$$

LeetCode 188：最多k次交易

这是最一般的情形，121和123都是它的特例。核心代码：

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++) {
            if (prices[i] > prices[i-1]) {
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }
    
    // dp[j][0] = 最多j次交易，不持有股票
    // dp[j][1] = 最多j次交易，持有股票
    int[][] dp = new int[k + 1][2];
    
    // 初始化：第一天买入后的状态
    for (int j = 1; j <= k; j++) {
        dp[j][1] = -prices[0];
    }
    
    for (int i = 1; i < n; i++) {
        // 必须倒序遍历k，避免状态污染
        for (int j = k; j >= 1; j--) {
            dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]);
            dp[j][1] = Math.max(dp[j][1], dp[j-1][0] - prices[i]);
        }
    }
    return dp[k][0];
}

这里有一个重要优化：当 $k \geq n/2$ 时，问题退化为无限次交易。因为一次完整的交易至少需要两天（买入一天，卖出一天），所以最多只能进行 $n/2$ 次交易。当 k 超过这个上限时，交易次数的约束就失去了意义。

为什么要倒序遍历 k？因为 dp[j][1] 依赖于 dp[j-1][0]。如果正序遍历，dp[j-1][0] 已经被更新为当前天的值，导致在同一天既买入又卖出，这是不允许的。

时间复杂度 $O(n \times k)$，空间复杂度 $O(k)$。

LeetCode 309：含冷冻期

冷冻期的约束是：卖出后必须等待一天才能买入。状态转移方程需要调整：

$$dp[i][0] = \max(dp[i-1][0], dp[i-1][1] + prices[i])$$$$dp[i][1] = \max(dp[i-1][1], dp[i-2][0] - prices[i])$$

买入时的转移从 i-1 变成了 i-2，因为买入必须在卖出后的第二天。

public int maxProfit(int[] prices) {
    int n = prices.length;
    if (n < 2) return 0;
    
    int[][] dp = new int[n][2];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    dp[1][0] = Math.max(0, prices[1] - prices[0]);
    dp[1][1] = Math.max(-prices[0], -prices[1]);
    
    for (int i = 2; 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-2][0] - prices[i]);
    }
    return dp[n-1][0];
}

空间优化版本：

public int maxProfit(int[] prices) {
    int dp0 = 0;                    // 今天不持有
    int dp1 = Integer.MIN_VALUE;    // 今天持有
    int dpPre0 = 0;                 // 昨天不持有（用于冷冻期）
    
    for (int price : prices) {
        int temp = dp0;
        dp0 = Math.max(dp0, dp1 + price);
        dp1 = Math.max(dp1, dpPre0 - price);
        dpPre0 = temp;
    }
    return dp0;
}

另一种视角是将状态分为三种：持有股票、不持有股票（可买入）、不持有股票（冷冻期）。这种三状态模型更直观：

public int maxProfit(int[] prices) {
    int hold = Integer.MIN_VALUE;   // 持有股票
    int sold = 0;                   // 刚卖出（冷冻期）
    int rest = 0;                   // 不持有，可买入
    
    for (int price : prices) {
        int prevHold = hold;
        int prevSold = sold;
        
        hold = Math.max(hold, rest - price);
        sold = prevHold + price;
        rest = Math.max(rest, prevSold);
    }
    return Math.max(sold, rest);
}

LeetCode 714：含手续费

手续费的约束更简单：每次交易扣除 fee。可以在买入时扣除，也可以在卖出时扣除——两者等价：

// 方案一：买入时扣除
public int maxProfit(int[] prices, int fee) {
    int dp0 = 0;
    int dp1 = Integer.MIN_VALUE;
    
    for (int price : prices) {
        int temp = dp0;
        dp0 = Math.max(dp0, dp1 + price);
        dp1 = Math.max(dp1, temp - price - fee);
    }
    return dp0;
}

// 方案二：卖出时扣除
public int maxProfit(int[] prices, int fee) {
    int dp0 = 0;
    int dp1 = Integer.MIN_VALUE;
    
    for (int price : prices) {
        int temp = dp0;
        dp0 = Math.max(dp0, dp1 + price - fee);
        dp1 = Math.max(dp1, temp - price);
    }
    return dp0;
}

注意使用 long 类型避免整数溢出，特别是当 prices[i] 和 fee 都很大时。

状态机DP的本质

股票问题系列展示了状态机DP的完整方法论：

第一步：定义状态。股票问题的核心状态是"是否持有股票"，加上"交易次数"这个维度。状态定义要满足两个条件：一是能够完全描述问题，二是状态之间有明确的转换关系。

第二步：画出状态图。状态图清晰展示了所有可能的转换路径。在股票问题中，从"不持有"可以通过"买入"转换到"持有"；从"持有"可以通过"卖出"转换到"不持有"。

第三步：写出转移方程。转移方程是状态图的数学表达。每个状态的值等于所有可能的前驱状态值加上转换代价的最大值。

第四步：处理边界条件。边界条件决定了动态规划的起点。股票问题中，“还没开始"和"不允许交易"是两种边界情况。

第五步：空间优化。当状态转移只依赖于前一个或前几个状态时，可以用滚动变量替代整个数组。

面试中的常见陷阱

陷阱一：混淆交易次数的定义。k 指的是最多允许的买入次数（或完整的买卖对数），而不是卖出次数。状态转移时，买入消耗一次额度，卖出不消耗。

陷阱二：状态更新顺序错误。空间优化时，必须保证用到的是上一轮的值。对于股票问题，通常需要倒序遍历 k，或用临时变量保存旧值。

陷阱三：边界条件遗漏。dp[0][1] = -prices[0] 还是 dp[0][1] = Integer.MIN_VALUE？这取决于状态定义。如果定义是"在第i天结束时持有股票”，则前者正确；如果定义是"在第i天进行了买入操作"，则需要更仔细考虑。

陷阱四：整数溢出。当 prices[i] 达到 $10^4$，fee 达到 $10^4$，且交易次数较多时，累加可能溢出。建议使用 long 类型，或在比较前检查边界。

统一模板总结

public int maxProfit(int[] prices) {
    // 基础状态：不持有/持有
    int dp0 = 0, dp1 = Integer.MIN_VALUE;
    
    for (int price : prices) {
        int temp = dp0;
        // 根据具体问题调整转移方程
        dp0 = Math.max(dp0, dp1 + price);        // 卖出或不操作
        dp1 = Math.max(dp1, temp - price);       // 买入或不操作
    }
    return dp0;
}

这个模板可以通过简单修改适应所有变体：

  • k=1：dp1 = Math.max(dp1, -price)
  • k=∞：dp1 = Math.max(dp1, temp - price)
  • 冷冻期：引入 dpPre0 变量
  • 手续费：买入或卖出时减去 fee
  • k次交易：扩展为二维数组 dp[k][2]

股票问题系列的魅力在于，它用最简洁的状态模型解释了动态规划的核心思想——状态定义、状态转移、边界处理。掌握这个框架后，类似的状态机DP问题（如打家劫舍系列、编辑距离系列）都将迎刃而解。

参考