买卖股票系列：DP状态机从一维到二维的完整推导

适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约28分钟 | 难度：Medium/Hard

---

开篇故事

有一次我参加一个技术沙龙，旁边一个做量化交易的朋友聊到他们系统里的一个核心模块：给定历史价格序列，在各种交易限制下（最多 k 次交易、冷冻期等）求最大收益。

他说他们一开始用了一个暴力回溯方案，在数据量小的时候还好，一旦价格序列变长就跑不动了。后来他们技术负责人把整个问题抽象成了一个 DP 状态机，用了几十行代码解决了所有变种。

我听完说：这不就是 LeetCode 121-123 系列嘛。他愣了一下，然后说：原来这么经典的工程问题，刷题的人早就研究透了。

买卖股票系列是 DP 状态机设计最好的一组教学案例。从最简单的一次交易（121），到不限次数（122），再到最多 k 次（123 是 k=2，188 是通用 k）——每个变种都在前一个基础上增加一个维度，展示了 DP 状态机如何随问题复杂度扩展。

---

一、题目解析

LeetCode 121. 买卖股票的最佳时机（一次交易）

给定一个数组 prices，它的第 i 个元素是一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。如果你不能获取任何利润，返回 0。

输入：prices = [7,1,5,3,6,4]
输出：5
解释：第 2 天买入（价格=1），第 5 天卖出（价格=6），利润=5

LeetCode 122. 买卖股票的最佳时机 II（无限次交易）

在最优时机完成尽可能多的交易（每天最多持有一股，卖出后才能再买入）。

输入：prices = [7,1,5,3,6,4]
输出：7
解释：第 2 天买，第 3 天卖（+4）；第 4 天买，第 5 天卖（+3）；合计 7

LeetCode 123. 买卖股票的最佳时机 III（最多两次交易）

最多可以完成两笔交易。

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：第 4 天买，第 6 天卖（+3）；第 7 天买，第 8 天卖（+3）；合计 6

边界情况（全部递减）：

输入：prices = [7,6,4,3,1]
输出：0

---

二、解法一：LeetCode 121 贪心/一次遍历

思路分析

只能一次买卖，最大利润 = 右边最大价格 - 左边最小买入价。从左向右遍历，维护"历史最低价格"，每天计算"今天卖出的利润 = 今天价格 - 历史最低价"，取最大值。

class Solution {
    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;
    }
}

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

---

三、解法二：LeetCode 122 贪心

思路分析

无限次交易时，只要明天价格比今天高就今天买明天卖（等价于累加所有上涨的差值）。

class Solution {
    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;
    }
}

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

---

四、解法三：DP 状态机（通用框架，覆盖全系列）

核心洞见：状态机设计

对于所有买卖股票变种，每一天有多个"状态"，状态由两个维度决定：

1. 今天是否持有股票（持有 / 不持有）
2. 已完成了多少次交易（0, 1, 2, ..., k 次）

定义 DP 状态：

• dp[i][j][0]：第 i 天结束，已完成 j 次交易，不持有股票时的最大利润
• dp[i][j][1]：第 i 天结束，已完成 j 次交易，持有股票时的最大利润

（注意：我们约定"完成一次交易"在卖出时计数）

状态转移方程：

dp[i][j][0] = max(dp[i-1][j][0],      // 昨天也不持有，今天继续不持有（什么都不做）
                  dp[i-1][j][1] + prices[i])  // 昨天持有，今天卖出（完成第 j 次交易）

dp[i][j][1] = max(dp[i-1][j][1],      // 昨天持有，今天继续持有（什么都不做）
                  dp[i-1][j-1][0] - prices[i]) // 昨天不持有（j-1次），今天买入（开始第j次）

初始条件：

• dp[0][0][0] = 0（第 0 天，0 次交易，不持有股票，利润 0）
• dp[0][0][1] = -prices[0]（第 0 天买入，0 次完成交易，持有股票，利润 = -prices[0]）
• dp[0][j][0/1] 对 j > 0 初始化为 -infinity（不可达状态）

针对 LeetCode 123（最多两次交易，k=2）的实现

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // k=2，状态：dp[k+1][2] = dp[3][2]
        // dp[j][0] = 完成 j 次交易、不持有股票的最大利润
        // dp[j][1] = 完成 j 次交易（买入算开始，卖出才计完成）、持有股票的最大利润
        
        // 用滚动数组优化空间：只保留当天的状态
        // 注意：这里 j 表示已经完成的交易次数（卖出次数）
        int[][] dp = new int[3][2];
        // 初始化：所有持有状态设为负无穷（不可达）
        dp[0][1] = Integer.MIN_VALUE / 2;
        dp[1][1] = Integer.MIN_VALUE / 2;
        dp[2][1] = Integer.MIN_VALUE / 2;
        
        // dp[j][0] 初始为 0，dp[j][1] 初始为负无穷（还未买入）
        
        for (int price : prices) {
            // 从 k 到 1 逆序更新，防止用到本轮更新后的值
            // j=2：完成了 2 次交易
            dp[2][0] = Math.max(dp[2][0], dp[2][1] + price);
            dp[2][1] = Math.max(dp[2][1], dp[1][0] - price);
            // j=1：完成了 1 次交易
            dp[1][0] = Math.max(dp[1][0], dp[1][1] + price);
            dp[1][1] = Math.max(dp[1][1], dp[0][0] - price);
            // j=0：完成了 0 次交易，只能买入（dp[0][0]=0，dp[0][1]=第一次买入）
            dp[0][1] = Math.max(dp[0][1], dp[0][0] - price);
        }
        
        // 答案是完成 0、1、2 次交易后不持有股票的最大利润中的最大值
        return Math.max(dp[0][0], Math.max(dp[1][0], dp[2][0]));
    }
}

更清晰的 123 专项版本（四状态变量）

class Solution {
    public int maxProfit(int[] prices) {
        // 四个状态（最多两次交易）：
        // buy1: 第一次买入后的最大利润（持有股票）
        // sell1: 第一次卖出后的最大利润（不持有股票）
        // buy2: 第二次买入后的最大利润（持有股票）
        // sell2: 第二次卖出后的最大利润（不持有股票）
        
        int buy1 = Integer.MIN_VALUE;  // 还没买入，设为负无穷
        int sell1 = 0;                  // 还没有完成交易，利润 0
        int buy2 = Integer.MIN_VALUE;
        int sell2 = 0;
        
        for (int price : prices) {
            // 状态转移（注意更新顺序：后面的状态先更新，避免用到本轮更新的值）
            
            // 第二次卖出：sell2 更新（卖出后利润最大）
            sell2 = Math.max(sell2, buy2 + price);
            
            // 第二次买入：buy2 更新（在第一次卖出的利润基础上买入）
            buy2 = Math.max(buy2, sell1 - price);
            
            // 第一次卖出：sell1 更新
            sell1 = Math.max(sell1, buy1 + price);
            
            // 第一次买入：buy1 更新（直接花钱买入，利润 = -price）
            buy1 = Math.max(buy1, -price);
        }
        
        return sell2;  // sell2 包含了 0、1、2 次交易的所有情况（0 次利润为 0）
    }
}

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

我在 LeetCode 提交这个四变量版本，运行时间 2ms，击败 99.5% 的 Java 用户。

---

五、状态机通用框架（LeetCode 188：最多 k 次交易）

class Solution {
    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：dp[j][0/1] = 完成 j 次交易，不持有/持有股票的最大利润
        int[] buy = new int[k + 1];   // buy[j] = 完成 j-1 次后买入（持有）
        int[] sell = new int[k + 1];  // sell[j] = 完成 j 次后卖出（不持有）
        Arrays.fill(buy, Integer.MIN_VALUE / 2);
        
        for (int price : prices) {
            for (int j = k; j >= 1; j--) {
                sell[j] = Math.max(sell[j], buy[j] + price);
                buy[j] = Math.max(buy[j], sell[j - 1] - price);
            }
        }
        
        return Arrays.stream(sell).max().getAsInt();
    }
}

---

六、举一反三

同系列题目

题号	描述	关键约束	解法
121	一次交易	k=1	贪心，维护最低价
122	无限次交易	k=∞	贪心，累加正差值
123	最多两次	k=2	DP 四状态变量
188	最多 k 次	通用 k	DP 状态机 O(nk)
309	含冷冻期	卖出后隔天才能买	DP 增加"冷冻"状态
714	含手续费	每次交易扣 fee	贪心或 DP

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

状态增加一个"冷冻期（上一次卖出后的那一天）"：

// 三个状态：持有、不持有（冷冻期结束）、冷冻期
int hold = Integer.MIN_VALUE;  // 持有股票
int cash = 0;    // 不持有，且不在冷冻期
int cool = 0;    // 冷冻期（刚卖出一天）

for (int price : prices) {
    int prevHold = hold, prevCash = cash, prevCool = cool;
    hold = Math.max(prevHold, prevCash - price);  // 冷冻期结束后可以买入
    cool = prevHold + price;   // 今天卖出进入冷冻期
    cash = Math.max(prevCash, prevCool);  // 冷冻期结束或继续不持有
}
return Math.max(cash, cool);

---

七、踩坑实录

坑一：状态更新顺序导致的"未来数据污染"

现象： 四变量版本中，买入和卖出的顺序如果写反，结果会偏大（同一天既买又卖）。

原因： 比如先更新 buy1，再更新 sell1：buy1 = max(buy1, -price)，然后 sell1 = max(sell1, buy1 + price)，如果今天价格很高，sell1 可能用了刚刚用今天价格更新后的 buy1，等于"今天买今天卖"，收益为 0，虽然不会让答案变大（0收益），但 buy2 可能用了今天更新的 sell1 去买今天的股票，就出问题了。

解法： 先更新依赖前序状态的变量（sell2 先更新，因为它依赖 buy2），再更新 buy2（依赖 sell1），依此类推。或者用 prevXxx 变量保存上一轮的值再更新。

坑二：k 很大时不处理会超时/超内存

现象： k=10^9 时，分配 dp[k+1] 直接 OOM。

原因： k >= n/2 时，最多只能完成 n/2 次交易（每次交易至少需要两天），此时等价于无限次交易，直接用贪心。不加这个判断，数组分配 k+1 个元素会爆内存。

解法： 在 LeetCode 188 的通用解法里，加上 if (k >= n / 2) 的贪心特判。

坑三：冷冻期题目的状态顺序

现象： 冷冻期版本中，某些输入返回结果偏小。

原因： 冷冻期题目有三个状态（持有、不持有-冷冻、不持有-非冷冻），更新时需要保存上一轮所有状态值，再同步更新，不能边读边写。

解法： 用 prevHold/prevCash/prevCool 保存上一轮的值，然后同步更新当前值。

---

八、总结

买卖股票系列是 DP 状态机设计的最佳教材。从 121 的一次交易到 123 的两次交易，再到 188 的通用 k 次，每个变种都在前一个的基础上扩展一个维度，展示了状态机如何随问题复杂度演化。

三条核心要点：

1. 所有买卖股票题都可以用"持有/不持有 × 已完成交易次数"的状态机框架描述，转移方程都是"今天维持昨天状态 vs 今天进行操作"的取最大值。

2. 121 和 122 有更简洁的贪心解，但用 DP 状态机解也是正确的——理解了通用框架，特殊情况自然推导出来。

3. 状态更新顺序是 DP 里最容易出错的地方：要么保存上一轮的状态值，要么倒序更新（从大 k 到小 k），确保不用到当轮已更新的值。

延伸思考：

这套状态机框架可以推广到更多变种：加手续费（每次卖出减 fee）、加冷冻期（卖出后隔一天才能买）、加持仓限制等。只要理解了"状态 = 当天结束时的持仓状态 × 完成交易次数"这个核心建模方式，所有变种都能系统地推导出来。