动态规划状态机精解：买卖股票的最佳时机 III 问题

1. 项目概述：理解“买卖股票的最佳时机 III”的核心挑战

买卖股票的问题，在算法面试和日常刷题中，绝对是高频中的高频。它不像一些纯数学推导的题目，而是完美地将现实世界的金融交易逻辑抽象成了一个动态规划模型，考察的是你如何将复杂约束转化为清晰的状态定义和转移方程。今天要拆解的这道123. 买卖股票的最佳时机 III，可以说是这个系列里承上启下的关键一题。它不再是简单的“只能买卖一次”（121题）或者“可以无限次买卖”（122题），而是加上了“最多可以完成两笔交易”这个核心限制。

这意味着什么？意味着你不能再像无限次买卖那样，简单地贪心每一天的上涨；也不能像单次买卖那样，只维护一个历史最低价。你必须精确地记录，在每一天结束时，你处于第几次交易、持有或不持有股票的状态。这直接引入了“状态机”的思想。很多朋友卡在这里，就是因为对“状态”的理解不够透彻，或者被“最多两次”这个条件搞晕了，不知道如何设计状态数组。我将带你从最朴素的想法开始，一步步推导出最优的动态规划解法，并给出可以直接“抄作业”的Python和C++代码。无论你是正在准备面试，还是想深入理解动态规划的状态设计，这篇文章都会让你有收获。

2. 核心思路拆解：从暴力搜索到状态机DP

2.1 问题重述与难点分析

题目通常这样描述：给定一个整数数组prices，它的第i个元素prices[i]是一支给定股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。这意味着，在任意一天结束时，你最多只能持有一股股票。

核心难点：

1. 交易次数限制：“最多两笔”是一个硬性上限，这直接决定了我们状态定义的维度。
2. 状态复杂性：每一天，你可能有多种“身份”：从未买过、第一次买入后持有、第一次卖出后空仓、第二次买入后持有、第二次卖出后空仓。我们需要一个清晰的方式描述这些身份。
3. 全局最优与局部决策：今天的决策（买、卖、持有、观望）会影响未来所有天的可能性，不能只看眼前利益。

2.2 思路演进：三维DP、二维DP与空间优化

最直观的想法是设计一个三维动态规划数组dp[i][k][0 or 1]。

• i：表示第i天（0 <= i < n）。
• k：表示剩余的交易次数（注意，这里“交易”指一次完整的“买入+卖出”，k最大为2）。有些定义喜欢用“已经完成”的交易次数，本质等价，但状态转移的方向不同。我更喜欢“剩余次数”，因为初始状态更清晰。
• 0 or 1：表示当前是否持有股票（0表示不持有，1表示持有）。

那么，dp[i][k][0]的含义就是：在第i天结束时，最多还能进行k次交易，且当前不持有股票，所能获得的最大利润。 同理，dp[i][k][1]表示在第i天结束时，最多还能进行k次交易，且当前持有股票，所能获得的最大利润。

我们最终要求的是dp[n-1][2][0]，即最后一天，最多还能进行2次交易（实际上可能没用完），且不持有股票的最大利润。持有股票的状态利润肯定低于不持有（因为股票要卖出才是利润），所以最终答案是不持有状态。

状态转移方程：

1. dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
   • 解释：今天不持有股票，有两种可能：
     • 昨天就不持有，今天继续观望：利润继承dp[i-1][k][0]。
     • 昨天持有，今天卖出：利润是昨天的持有利润dp[i-1][k][1]加上今天卖出的收入prices[i]。注意，卖出操作不消耗剩余交易次数k，因为交易次数是在买入时扣减的（这是一个关键理解点，也有定义在卖出时扣减，只要自洽即可）。
2. dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k+1][0] - prices[i])
   • 解释：今天持有股票，有两种可能：
     • 昨天就持有，今天继续持有：利润继承dp[i-1][k][1]。
     • 昨天不持有，今天买入：利润是昨天在交易次数多一次（即k+1）的状态下的不持有利润dp[i-1][k+1][0]，减去今天买入的成本prices[i]。注意：因为今天买入后，剩余交易次数从k+1变成了k，所以参考的是dp[i-1][k+1][0]。

初始状态（基准情况）：

• dp[-1][...][0] = 0：天数从0开始，但我们可以想象第-1天（交易开始前），不持有股票的利润是0。
• dp[-1][...][1] = -infinity：交易开始前，不可能持有股票，用负无穷表示不可达。
• dp[...][0][0] = 0：如果剩余交易次数为0，不允许再买入，那么不持有股票的最大利润就是0（无法进行任何交易）。
• dp[...][0][1] = -infinity：剩余交易次数为0时，不允许持有股票，用负无穷表示。

这个三维DP思路非常清晰，但空间复杂度是 O(n * 3 * 2)。由于k只有0,1,2三种可能，我们可以将其展开，降维成二维DP，用五个变量来表示每一天的五个关键状态，这也就是常说的“状态机”DP，也是本题最优解的核心。

3. 状态机DP详解与五状态法

3.1 五个状态的定义

既然k很小（0,1,2），我们可以直接枚举出所有有意义的状态组合。关键在于理解，k代表剩余次数，但结合是否持有，我们可以定义出五个清晰的状态，它们贯穿整个交易过程：

1. buy1: 进行过第一次买入操作后，当前持有第一支股票的状态下的最大利润。对应三维DP中的dp[i][2][1]（剩余2次交易，持有股票，但这是第一次买入后的持有）。
2. sell1: 进行过第一次卖出操作后，当前不持有股票的状态下的最大利润。对应三维DP中的dp[i][1][0]（剩余1次交易，不持有股票）。
3. buy2: 进行过第二次买入操作后，当前持有第二支股票的状态下的最大利润。对应三维DP中的dp[i][1][1]（剩余1次交易，持有股票）。
4. sell2: 进行过第二次卖出操作后，当前不持有股票的状态下的最大利润。对应三维DP中的dp[i][0][0]（剩余0次交易，不持有股票）。
5. rest: 一个辅助状态，表示从未进行过任何交易，利润始终为0。在迭代中，它隐含在初始化里。

注意：这里的状态定义是“进行过某次操作后”，这是一个非常巧妙且实用的定义。它使得状态转移变得直观：buy1只能从rest或buy1转移来；sell1只能从buy1转移来；buy2只能从sell1转移来；sell2只能从buy2转移来。

3.2 状态转移方程与解释

我们用buy1[i],sell1[i],buy2[i],sell2[i]分别表示第i天结束时的对应状态的最大利润。

初始化（第0天，i=0）:

• buy1[0] = -prices[0]：如果第一天就买入，利润是负的股价。
• sell1[0] = 0：第一天不可能完成第一次卖出（因为还没买入），所以利润为0。另一种理解是，在同一天买入并卖出，利润为0，但题目通常不允许。
• buy2[0] = -prices[0]：第一天就进行第二次买入？这看起来不合理，因为第一次交易还没完成。但实际上，这个状态可以被理解为“在同一天内完成了第一次买卖（利润0），然后又进行了第二次买入”。在动态规划中，我们需要允许这种“状态存在但利润极差”的情况，它会在后续被更优的状态覆盖。初始化为-prices[0]是安全的。
• sell2[0] = 0：同理，第一天不可能完成第二次卖出。

状态转移（对于 i > 0）:

1. buy1[i] = max(buy1[i-1], -prices[i])
   • buy1[i-1]: 昨天就已经是第一次买入后的持有状态，今天继续持有。
   • -prices[i]: 今天才进行第一次买入。注意，因为是第一次买入，之前利润为0，所以买入后的利润直接是-prices[i]。这个max操作保证了我们总是在更低的股价买入。
2. sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i])
   • sell1[i-1]: 昨天就已经完成第一次卖出，今天继续空仓。
   • buy1[i-1] + prices[i]: 昨天持有第一支股票，今天卖出。利润是昨天的持有利润加上今天卖出的收入。
3. buy2[i] = max(buy2[i-1], sell1[i-1] - prices[i])
   • buy2[i-1]: 昨天就已经是第二次买入后的持有状态，今天继续持有。
   • sell1[i-1] - prices[i]: 昨天完成了第一次卖出，今天用所得利润进行第二次买入。
4. sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i])
   • sell2[i-1]: 昨天就已经完成第二次卖出，今天继续空仓。
   • buy2[i-1] + prices[i]: 昨天持有第二支股票，今天卖出。

最终答案：max(sell1[n-1], sell2[n-1])。实际上，由于sell2包含了完成两笔交易的可能，其利润不会低于只完成一笔交易的sell1，所以答案就是sell2[n-1]。

3.3 空间优化：滚动变量

观察状态转移方程，第i天的状态只依赖于第i-1天的状态。因此，我们完全不需要维护整个数组，只需要四个变量在每一天滚动更新即可。这是动态规划常见的空间优化技巧。

定义四个变量：

• buy1: 当前第一次买入后的最大利润。
• sell1: 当前第一次卖出后的最大利润。
• buy2: 当前第二次买入后的最大利润。
• sell2: 当前第二次卖出后的最大利润。

初始化：buy1 = buy2 = -prices[0]sell1 = sell2 = 0

遍历prices(从第1天开始，即i=1)：

for price in prices[1:]: buy1 = max(buy1, -price) # 可以是今天才第一次买 sell1 = max(sell1, buy1 + price) # 可以是今天第一次卖 buy2 = max(buy2, sell1 - price) # 可以是今天第二次买 sell2 = max(sell2, buy2 + price) # 可以是今天第二次卖

注意更新顺序！buy1和sell1要用到旧的值，buy2要用到更新前的sell1，sell2要用到更新前的buy2。上面的写法在Python中是安全的，因为赋值语句是顺序执行的。但在一些其他语言或理解上，更严谨的做法是使用临时变量保存旧值。

4. 完整代码实现与逐行解析

4.1 Python 代码实现

from typing import List class Solution: def maxProfit(self, prices: List[int]) -> int: """ 计算最多完成两笔交易的最大利润。 参数: prices (List[int]): 股票每日价格列表 返回: int: 最大利润 """ n = len(prices) if n < 2: return 0 # 无法完成任何交易 # 初始化四个状态变量 # buy1: 第一次买入后，持有的最大利润（负数，表示成本） # sell1: 第一次卖出后，不持有的最大利润 # buy2: 第二次买入后，持有的最大利润 # sell2: 第二次卖出后，不持有的最大利润（即最终答案） buy1 = buy2 = -prices[0] # 第一天如果买入，利润为负的股价 sell1 = sell2 = 0 # 第一天无法卖出，利润为0 # 从第二天开始遍历 for i in range(1, n): # 保存旧值，用于本轮的顺序计算（非必须，但逻辑更清晰） # 在Python中，由于下面计算是立即赋值的，且buy1, sell1等是标量， # 直接使用当前值进行计算，其依赖的是上一轮迭代后的值，所以顺序写即可。 # 但为了与状态转移方程严格对应，我们可以这样理解： # new_buy1 = max(buy1, -prices[i]) # new_sell1 = max(sell1, buy1 + prices[i]) # 这里的buy1是旧的 # new_buy2 = max(buy2, sell1 - prices[i]) # 这里的sell1是旧的 # new_sell2 = max(sell2, buy2 + prices[i]) # 这里的buy2是旧的 # 然后同时赋值: buy1, sell1, buy2, sell2 = new_buy1, new_sell1, new_buy2, new_sell2 # 实际简洁写法（依赖语言特性，结果正确）： buy1 = max(buy1, -prices[i]) sell1 = max(sell1, buy1 + prices[i]) buy2 = max(buy2, sell1 - prices[i]) sell2 = max(sell2, buy2 + prices[i]) # 更严谨的、避免顺序依赖的写法： # prev_buy1, prev_sell1, prev_buy2, prev_sell2 = buy1, sell1, buy2, sell2 # buy1 = max(prev_buy1, -prices[i]) # sell1 = max(prev_sell1, prev_buy1 + prices[i]) # buy2 = max(prev_buy2, prev_sell1 - prices[i]) # sell2 = max(prev_sell2, prev_buy2 + prices[i]) # 最终最大利润是第二次卖出后的状态，因为它包含了完成0,1,2次交易的所有可能最优解 return sell2

代码解析:

1. 边界处理：如果价格天数少于2，无法完成买入并卖出，直接返回0。
2. 初始化：将buy1和buy2初始化为-prices[0]，表示如果第一天就买入（无论是第一次还是第二次），当前的利润（实际上是负的成本）。sell1和sell2初始化为0。
3. 核心循环：从第二天开始遍历。循环体内的四行代码，严格对应了上一节推导出的四个状态转移方程。
4. 返回值：返回sell2。为什么不是max(sell1, sell2)？因为在状态转移中，sell2的更新总是参考了sell1的结果（通过buy2）。如果只完成一次交易是最优的，那么在迭代过程中，sell2会通过max(sell2, buy2 + price)中的buy2（可能为负）和sell2（继承之前的sell1）来保持最大值。可以证明sell2最终一定不小于sell1。所以直接返回sell2即可。

4.2 C++ 代码实现

#include <vector> #include <algorithm> using namespace std; class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if (n < 2) return 0; // 初始化四个状态 int buy1 = -prices[0]; int sell1 = 0; int buy2 = -prices[0]; int sell2 = 0; // 遍历价格数组 for (int i = 1; i < n; ++i) { // 使用临时变量保存前一天的状态，确保更新顺序正确 int prev_buy1 = buy1; int prev_sell1 = sell1; int prev_buy2 = buy2; int prev_sell2 = sell2; // 根据状态转移方程更新 buy1 = max(prev_buy1, -prices[i]); // 第一次买入 sell1 = max(prev_sell1, prev_buy1 + prices[i]); // 第一次卖出 buy2 = max(prev_buy2, prev_sell1 - prices[i]); // 第二次买入 sell2 = max(prev_sell2, prev_buy2 + prices[i]); // 第二次卖出 // 也可以写成更紧凑但可能不易理解的形式（依赖求值顺序，在C++中也是从左到右）： // sell2 = max(sell2, buy2 + prices[i]); // buy2 = max(buy2, sell1 - prices[i]); // sell1 = max(sell1, buy1 + prices[i]); // buy1 = max(buy1, -prices[i]); // 注意：这种紧凑写法中，等号右边的变量值是上一轮的值，因为赋值尚未发生。 // 但为了绝对清晰和避免混淆，推荐使用临时变量的写法。 } return sell2; } };

C++代码要点：

1. 头文件：使用<vector>和<algorithm>分别用于容器和max函数。
2. 临时变量：在C++中，我显式地使用了prev_*临时变量来保存前一天的状态。这是最安全、最清晰的做法，完全避免了因更新顺序可能带来的歧义。虽然像Python那样顺序写也可能得到正确结果（因为表达式求值在赋值之前），但显式保存旧值是好习惯。
3. 返回值：同样是返回sell2。

5. 实战演练与案例分析

理论说再多，不如看几个具体的例子，走一遍状态转移的过程，感受一下算法是如何工作的。

5.1 案例一：标准波动市场prices = [3,3,5,0,0,3,1,4]

这个序列有涨有跌，是检验算法的好例子。

最终结果：sell2 = 6。对应的最优操作路径是：(买@3, 卖@5)利润2，(买@0, 卖@4)利润4。注意，实际操作中，买入卖出日期不能重叠，但这里“第3天0元买”指的是 prices[3]=0 的那天，与第一次卖出 prices[2]=5 不冲突。

5.2 案例二：单调上涨市场prices = [1,2,3,4,5]

在无限次交易中，利润就是所有上涨之和4。但这里限制两次交易。

最终结果：sell2 = 4。最优策略是只进行一次交易：第0天1元买入，第4天5元卖出，利润4。因为市场单调上涨，一次交易就能捕捉全部涨幅，第二次交易没有增加利润的空间。算法正确地得到了这个结果。

5.3 案例三：单调下跌市场prices = [5,4,3,2,1]

最终结果：sell2 = 0。任何交易都会亏损，所以最优策略是不交易，利润为0。

通过这些案例，可以看到状态机是如何动态地追踪“在某个阶段，进行到第几次交易、持有或不持有”的最佳利润的。

6. 常见问题与深度思考

6.1 为什么buy2要初始化为-prices[0]？

这是一个容易困惑的点。从实际意义上讲，第一天不可能完成第一次交易后再进行第二次买入。但在动态规划中，我们初始化的是“状态”的可能利润值。初始化为-prices[0]是一个“安全”的初始值，它表示一种“理论上可能但实际很差”的情况：假设在同一天（第0天）我们以prices[0]的价格完成了第一次买卖（利润为0），然后又以prices[0]的价格买入了第二次。这样初始的buy2利润就是-prices[0]。在后续的max比较中，如果存在更优的第二次买入时机（比如用第一次卖出后的正利润去买入），这个很差的初始值会被覆盖掉。如果初始化为0或一个很大的正数，可能会错误地影响max操作。

6.2 状态转移的顺序可以调换吗？

在使用了临时变量保存旧值的前提下，四个状态的更新顺序是可以调换的，因为新状态都只依赖于旧状态，彼此之间没有依赖。例如，先更新sell2，再更新buy2，再更新sell1，最后更新buy1，只要计算时用的都是prev_*值，结果就是正确的。

但是，在没有使用临时变量、直接进行顺序赋值的情况下（如Python简洁写法），顺序是至关重要的。必须按照buy1 -> sell1 -> buy2 -> sell2的顺序。因为：

• sell1的计算依赖于当前的buy1（我们希望是旧的buy1）。
• buy2的计算依赖于当前的sell1（我们希望是旧的sell1）。
• sell2的计算依赖于当前的buy2（我们希望是旧的buy2）。

Python的简洁写法之所以正确，正是因为赋值语句是顺序执行的。当计算sell1 = max(sell1, buy1 + price)时，等号右边的buy1是上一轮迭代后的值（即旧的buy1），因为本轮对buy1的赋值已经完成。这是一种“隐式”地使用了旧值。为了代码清晰和跨语言一致性，我强烈推荐使用临时变量的写法，这样逻辑一目了然，也不容易出错。

6.3 如何扩展到“最多交易 k 次”？

这是本题的自然延伸（LeetCode 188. 买卖股票的最佳时机 IV）。思路完全一致，只是状态变量从4个变成了2*k个（buy1, sell1, buy2, sell2, ..., buyk, sellk）。我们可以用两个长度为k+1的数组buy和sell来表示，其中buy[j]表示进行完第j次买入（持有第 j 支股票）后的最大利润，sell[j]表示进行完第j次卖出后的最大利润。状态转移方程为：

for j in range(1, k+1): buy[j] = max(buy[j], sell[j-1] - price) sell[j] = max(sell[j], buy[j] + price)

初始化时，buy[1..k] = -prices[0],sell[0..k] = 0。最终答案是sell[k]。当k很大时（比如k > n/2），问题退化为无限次交易，可以用贪心解决以优化时间。

6.4 如果包含交易手续费或冷冻期呢？

这是买卖股票问题的另外两个经典变种。

• 含手续费（LeetCode 714）：在每次卖出的时候，从利润中减去手续费fee即可。状态转移方程修改为：sell = max(sell, buy + price - fee)（对于无限次交易）或对应地修改sell1,sell2。
• 含冷冻期（LeetCode 309）：卖出后需要等待一天才能再次买入。这需要引入第三个状态cooldown（冷冻期），或者更简单地，在买入的状态转移时，不是从sell转移，而是从两天前的sell（即sell[i-2]）转移。对于本题（最多两次交易），状态会变得复杂，但原理相通：buy2[i] = max(buy2[i-1], sell1[i-2] - prices[i])。

6.5 如何输出具体的交易日期？

动态规划通常只记录最大利润。要输出具体的买卖日期，需要额外记录状态转移的路径。我们可以用另一个数组path，在每次状态发生“转移”（即max选择了后者）时，记录下当前的天数i和是哪个操作（如“第一次买入”、“第一次卖出”等）。最后从最终状态sell2倒推回去，就能重构出最优的交易序列。这是一个经典的动态规划路径还原问题，在面试中有时会被问到。

7. 总结与个人心得

买卖股票 III 这道题，是理解动态规划中“状态机”思想的绝佳例题。它教会我们的不仅仅是解一道题，而是一种建模方法：将复杂的过程分解为几个离散的状态，定义清楚每个状态的含义，然后找出状态之间如何转移。

我个人的几点实操心得：

1. “剩余次数” vs “已完成次数”：我个人更喜欢“剩余次数”的定义，因为初始状态（剩余k次）很清晰。但无论哪种定义，只要状态转移方程自洽，最终都能得出正确结果。关键是理解其本质。
2. 空间优化是最后一步：不要一开始就追求最优的空间复杂度。先写出清晰易懂的三维或二维DP，确保逻辑正确。然后再观察状态依赖，进行空间优化（滚动数组、变量）。这样思路更清晰，调试也更容易。
3. 画状态转移图：在纸上画出几个状态（buy1,sell1,buy2,sell2）以及它们之间的转移关系（观望、买入、卖出），对于理解问题有奇效。这就像是一个小小的自动机。
4. 测试用例要全面：不要只测递增或递减序列。要测试波峰波谷、平台期、以及边界情况（如空数组、单元素数组）。像[1,2,4,2,5,7,2,4,9,0]这种有多个波动的序列，能很好地检验算法是否真的找到了全局最优的两笔交易。
5. 理解max操作的涵义：动态规划中的max，代表的是“到当前位置为止，处于该状态下的最优解”。它可能继承自前一天的同状态（不作为），也可能由其他状态通过一次操作转移而来（作为）。这个“最优子结构”是动态规划可行的核心。

最后，代码的简洁性固然重要，但清晰性和正确性永远是第一位的。在面试中，即使你写不出空间优化到O(1)的版本，只要能清晰地阐述三维DP的思路并写出正确的状态转移方程，就已经能拿到大部分分数了。当然，如果你能流畅地写出最终的五状态法并解释清楚，绝对是加分项。希望这篇详细的拆解能帮助你彻底拿下这道题，并将其背后的思想应用到更多动态规划问题中去。