LeetCode 第 123 题“买卖股票的最佳时机 III”是所有股票系列动态规划题里最考验状态设计的一道。只用 Python 写出来可能不到二十行但很多人卡在三十分钟都想不明白为什么一轮遍历就能把两笔交易一起算答案就在于把交易过程按“第几次买卖”拆成五个阶段用四个变量不断更新。这篇文章会把题目拆开把状态转移方程推导出来再带着你手跑一遍示例最后分享我在实际刷题时踩过的几个坑以及怎么把这种解法推广到“最多 k 次交易”的进阶题。适合看这篇文章的有两类人一类正在准备算法面试想快速掌握这题的通解另一类是学动态规划学到状态机部分需要一个看得懂的案例。如果你已经做过只能交易一次的 121 和无限次交易的 122那理解起来会更快哪怕你之前只写过一点简单 DP只要愿意跟着推一遍转移方程后面也能自己把代码写出来。1. 先把问题拆开再动手1.1 这题到底在求什么题目输入一个数组 prices长度为 nprices[i] 表示第 i 天的股价。你每天只能做三个动作之一买入一股、卖出一股、什么都不做。还有一个硬性约束在你完成第二笔买入之前必须先完成第一笔卖出卖出股票之后当天可以再买入但不能同时持有两只股票。目标很简单——全程最多进行两次“买入-卖出”让最后的现金减去初始现金的净收益最大。举一个官方示例prices [3, 3, 5, 0, 0, 3, 1, 4]。这个数组可以这样看第 1、2 天都是 3第 3 天涨到 5第 4、5 天跌到 0第 6 天反弹到 3第 7 天再跌到 1第 8 天涨到 4。最优操作是第 4 天以 0 买入、第 6 天以 3 卖出赚 3然后第 7 天以 1 买入、第 8 天以 4 卖出再赚 3。总利润 6。如果把第一次买入放第 2 天、卖出放第 3 天只赚 2虽然也是两次交易但不如上面的选择。所以“最多两笔”不等于“一定做满两笔”你可以只做一笔甚至一笔都不做。题目描述本身很短但“两笔交易之间有时间先后”这个细节决定了解法注定不是单纯找两个最大差值拼起来。你需要一个能把交易次序自然记录下来的一套框架而不是靠肉眼挑段。1.2 两遍贪心为什么不行有人一上来会这么想第一遍先找整个区间利润最大的一买一卖找到后把它标记掉第二遍在剩下的“空白区间”里再找一买一卖把两个利润相加。这个思路听着顺实际很容易被反例击穿。拿 prices [5, 0, 5, 100, 0, 100] 来说如果先做全局最大单笔交易你会发现 0 买入 100 卖出能赚 100线段从第 2 天跨到第 5 天。做完这单之后剩下的价格区间只有第 6 天一个 100再也没有卖出机会总利润 100。可最优解明明是先 0 买 5 卖赚 5再 0 买 100 卖赚 100总利润 105。你的第一笔贪心选择把后来更大的机会直接堵死了。也有人会退一步用“从左到右记录最大利润再从右到左记录最大利润最后枚举分割点”的前后缀法。这个思路也能出正确答案但需要额外开两个数组逻辑上要同时维护“第一笔”和“第二笔”两个视角。它能帮你直观理解答案却不是最容易推广到任意交易次数的方法。动态规划状态机则用一个统一模板解决 121、123、188 这一整个系列后面你甚至会不再想用前后缀法硬凑。1.3 它在股票系列里的位置股票买卖这一组题在 LeetCode 上是个完整的小家族。121 题只允许一笔交易一重循环记录历史最低价就行122 题可以无限次交易直接把每个相邻上涨差值累加123 题把交易次数卡死在两次188 题进一步推广到最多 k 次309 题加了卖出后必须隔一天的冷冻期714 题每次卖出都要交手续费。123 在中间扮演桥梁作用交易次数有限但又不算太多正好能体现状态机价值。很多人做完 121 和 122 之后再碰 123会觉得既不像 121 那样简单也不像 122 那样能无脑贪心。它要求你引入“第几笔”这个维度。理解这一题之后再看 188 基本只是把几个变量换成数组学习成本很低。2. 动态规划状态机设计2.1 把交易过程拆成五个阶段两次买卖对应的动作序列是买入一、卖出一、买入二、卖出二。站在任意一天收盘时你只可能处于五种情况之一还没买过买了第一支还没卖卖了第一支但还没买第二支买了第二支还没卖完成了第二笔卖出。最后一个就是最终状态。不过我们真正需要记忆的只有四个数值为什么因为“还没买过”状态始终是 0它表示初始手里有 0 元现金不会因为价格变化而改变不需要单独维护。于是剩下的四个状态我习惯命名成买 1、卖 1、买 2、卖 2。买 1 表示“持有一支股票时的最大现金余额”因为买入要付钱它在大部分时候是负数卖 1 表示“完成第一笔卖出后的最大现金余额”买 2 表示“买入第二支股票后的最大现金余额”卖 2 表示“完成第二笔卖出后的最大现金余额”。数组遍历结束后返回的卖 2 就是总利润。这里有个容易绕晕的点为什么不直接存“第一笔赚了多少”和“第二笔赚了多少”而是要存现金余额因为第二笔买入的成本 第一笔卖出后的现金 - 当前价格它是一个存量不是一个独立增量。你用现金视角看所有转移都变成了加法和减法推导起来超级顺。现金视角说白了就是把自己当成一个只有 0 元本金的人买入时现金减少卖出时现金增加最后手里的现金就是获利。2.2 四个转移方程怎么来的每天开始时你可以什么都不做也可以选择用当天的价格完成一次买入或卖出。什么都不做意味着状态原样保留所以在状态机上每个新值都至少有“保持原值”这个候选而如果做出动作就从前一个阶段迁移过来。四个方程如下买 1 max(买 1, 0 - price)卖 1 max(卖 1, 买 1 price)买 2 max(买 2, 卖 1 - price)卖 2 max(卖 2, 买 2 price)第一个方程表示要么什么都不做维持原来的买 1要么花掉 price 元买入第一支现金变成负的 price。第二个方程表示如果手里已经按最优成本持有第一支那卖出后现金增加 price。第三个方程是这题的精髓买第二支的钱不是凭空出现的它来自第一笔卖出后的现金存量所以是卖 1 - price。最后一个方程同理把第二支卖掉后得到卖 2。你可能会问既然买 1 可能在一笔交易之后被更新那卖 1 用的买 1 是不是“当天”的值对这个写法允许同一天先卖后买甚至允许在价格不理想时不动作。同一天完成一卖一买实际上净利润变化为零不会让答案变大所以不用额外限制。真正需要保证的是必须“卖出状态在前、买入状态在后”也就是代码里写卖 1 永远用更新后的买 1买 2 永远用更新后的卖 1状态链条不能倒。2.3 初始化和边界条件在第 0 天也就是 prices[0] 那天你只能选择买入不能刚买入刚卖出就凭空有收益。所以买 1 的初始值是 -prices[0]表示花掉当天价格买一支卖 1 初始为 0表示我没卖现金还是 0。买 2 和卖 2 的初值有点讲究常见写法把买 2 也设成 -prices[0]实际上等于允许第 0 天做“买了又卖、卖了再买”这种无意义操作因为买 2 max(-prices[0], 卖 1 - prices[0])而卖 1 一开始是 0所以两者相等。卖 2 初始为 0表示不完成第二笔交易利润就是 0。如果输入数组为空直接返回 0。别小看这一行很多边界测试用例一上来就是空数组代表没有股票可买。代码里如果不判空取 prices[0] 会直接抛异常。养成习惯处理任意数组题先想长度为 0、长度为 1 的情况。在我第一次写这题时把买 1、买 2 都初始化为 0结果遇到一直下跌的数组时答案正确但遇到先涨后跌的数组就全乱套。追问原因是因为 0 被当成“没有买入的现金”相当于我可以在第一天免费获得一股这样买 1 状态永远偏向 0后续卖出时利润会被大幅高估。记住买入是一项负债不是资产初始值必须是负价。3. Python 代码实现与逐步验证3.1 直接可跑的压缩版代码下面是压缩了空间后的版本只有四个整数变量在滚动更新from typing import List class Solution: def maxProfit(self, prices: List[int]) - int: if not prices: return 0 buy1 buy2 -prices[0] sell1 sell2 0 for price in prices[1:]: buy1 max(buy1, -price) sell1 max(sell1, buy1 price) buy2 max(buy2, sell1 - price) sell2 max(sell2, buy2 price) return sell2这段代码的更新顺序非常关键先更新买 1再更新卖 1然后才轮到买 2、卖 2。为什么不能把卖 1 放最前面因为如果先算卖 1它用的还是昨天的买 1今天新出现的低买机会要等到下一天才能用于卖出相当于把一整天的信息延后了严格来说可能丢掉当日高低价夹住的利润。虽然很多用例下结果也正确但状态机讲究的是像流水线一样推进每步都基于当天的前置状态顺序写错很难排查。最后返回 sell2而不是 sell1。sell2 已经包含了只做一笔交易的情况因为当你只做一笔时sell2 会等于 sell1。如果你做两笔sell2 自然更大。如果为了初学更容易理解可以先不压缩开四个长度为 n 的数组记录每天的状态最后把数组退化成变量。数组版本的好处是能打印出来观察状态变化坏处是空间变 O(n)。面试时说出“可以先开数组方便理解再优化成 O(1)”通常印象分会好一点。3.2 用示例数组手动跑一遍我用上面官方示例 prices [3, 3, 5, 0, 0, 3, 1, 4] 手跑一次看四个变量怎么变。下表里第 0 行是初始状态第 1 到第 7 行对应遍历 prices[1:] 时每轮的结束值天数pricebuy1sell1buy2sell2初始3-30-3013-30-3025-32-32300222400222530325610325740426这个表值得多看两眼。第 3 天价格跌到 0buy1 从 -3 变成 0因为“买入一支股票后手里现金 0 元”比“花 3 元买”更优所以第一笔的买入成本被更新到了 0 元同时 buy2 从 -3 变成 2因为卖 1 2 元再花 0 元买第二支手里还剩 2 元现金。第 5 天价格到 3sell1 从 2 变成 3sell2 从 2 变成 5这就是把第一支以 3 卖出、第二支也以 3 卖出后的累计现金。最后一天 price 4sell2 更新成 6对应第一支 0 买 3 卖赚 3第二支 1 买 4 卖赚 3。很多人看表格会觉得“buy1 变成了 0 很奇怪0 不是没买吗”注意这里 0 是“买股票花的钱为 0”跟“状态尚未发生”的 0 是两码事。在价格是 0 的天数买入成本就是 0所以现金余额依然为 0。这种细节正是动态规划状态机最需要跨过的坎每个变量代表的永远是某个动作发生后的现金余额而不是动作本身。3.3 复杂度分析时间上代码只遍历了一遍 prices 数组每天做四次 max 比较所以时间复杂度是 O(n)n 是数组长度。空间上只有 buy1、sell1、buy2、sell2 四个整数变量和输入规模无关所以是 O(1)。这样写出来的代码在 LeetCode 的 123 题面前已经是理论上的最优复杂度。如果面试官追问“能不能再快”答案是不能低于 O(n)因为你至少要看一眼每天的价格才能决定哪里买卖空间 O(1) 也已经足够紧凑不存在继续优化的必要。4. 常见错误与调试经验4.1 五个高频坑每个我都踩过第一个坑是初始值错误。把 buy1、buy2 设成 0 是最常见的原因是我前面说的“把买入当资产”的思维误区。第二个坑是不判空数组空输入直接崩。第三个坑是把返回结果写成 sell1漏掉了第二个交易可能带来的利润。第四个坑是状态顺序写错比如写完 buy1 之后直接写 buy2跳过 sell1导致第二笔交易永远无法启动或者启动得莫名其妙。第五个坑是在一个很长的 max 表达式里漏括号比如 max(buy1, -price) 和 max(buy1, -price, 0) 看起来相近但一个是“最优买入现金”一个混入了“从未持有”的 0会让状态语义完全混掉。另外一个隐蔽的坑是没有区分“最多两笔”和“正好两笔”。题目是“最多两笔”所以答案是 sell2 而不是 max(sell2, sell1)。其实因为 sell2 天然包含 sell1 的最优结果用 sell2 没问题但如果你写的是 max(sell2, sell1)也不算错只是多余。真正错的是把值拆成“第一次赚 第二次赚”然后相加时重复计算。4.2 现场调试的三板斧如果代码输出不对别急着乱改。我习惯按三步来第一步拿最短的数组手推边界比如 [1,2]、[2,1]、[3,3,3]第二步在循环里打印当天的 price、buy1、sell1、buy2、sell2看状态变化是否符合预期第三步写一个最朴素的四层循环暴力枚举把状态机答案和暴力答案对拍跑随机生成的小数组。暴力枚举虽然慢但它逻辑简单、不容易写错是验证动态规划正确性最好的裁判。def brute(prices): n len(prices) ans 0 for i in range(n): for j in range(i, n): profit1 prices[j] - prices[i] for x in range(j 1, n): for y in range(x, n): ans max(ans, profit1 prices[y] - prices[x]) return ans对拍的时候注意生成的价格范围小一点比如 0 到 20 之间长度不超过 8这样四层循环跑得动。把随机例子跑几千次还不冲突基本可以确定主解法是对的。这个对拍套路不止适用于股票题任何 O(n) 的迭代式 DP 我都很喜欢用它验证省心又不容易翻车。4.3 边界用例速查我整理了几组常用测试数据写代码前后都可以快速过一遍输入期望输出说明[]0空数组[1]0只有一天无法卖出[1, 2]1做一笔更优[2, 1]0一路下跌不交易[1, 2, 3]2一次做满也有 2[5, 0, 5, 100, 0, 100]105前面讲过的贪心反例这组用例完全可以拿去当单元测试也能在面试时作为自测样例。尤其是 [5, 0, 5, 100, 0, 100]专门验证你是不是真的避开了“先做最大单笔”的诱惑。5. 举一反三从两次推广到任意 k 次5.1 四个变量变成两个数组既然你已经理解了“最多两次”的状态机把次数改成“最多 k 次”就水到渠成不再单独写 buy1、sell1、buy2、sell2而是准备两个长度为 k1 的数组 buy 和 sell。buy[j] 表示完成了 j-1 笔交易后又买入第 j 支股票时的最大现金sell[j] 表示完成第 j 笔卖出后的最大现金。更新公式就两行buy[j] max(buy[j], sell[j - 1] - price) sell[j] max(sell[j], buy[j] price)唯一需要留神的是循环顺序。由于 sell[j-1] 已经在本天被更新过所以代码允许“同一天先卖后买”的连续性这种连续性不会让答案变大却简化了实现是常见写法。如果 k 非常大比如 k 超过 n // 2那么交易次数的限制已经近乎失效因为数组只有 n 天最多也只能完成 n // 2 对买卖。此时可以退化成 122 的贪心解法把每个正差值累加避免开一个大数组浪费时间。5.2 结合面试场景的一点个人经验我在刚学这题时有一段时间只看题解不手推结果面试中遇到参数变化就发慌。后来把整个股票系列集中刷了一遍发现它们就像同一栋楼的不同房间121 是观察历史最低价122 是贪心吃所有上涨123 是固定两层状态机188 是把双层状态机套进循环309 和 714 只是在状态转移上多加一条规则。这道 123 题真正训练的不是记住四行转移方程而是“把一个时间过程按阶段切分每个阶段只保留一个数值”的动态规划思维。这种思维换个场景照样用比如带购买上限的背包、受限的序列决策问题本质都是给状态降维。一个额外的面试小技巧讲这题的时候先说“我把交易次数看成状态的一个维度”比上来就报 buy1、sell1 更能让面试官听懂。因为你先交代建模思路再展开方程整个过程显得有层次。实际手写时先在白板上写清楚四行方程再开始编码速度也会快很多。如果你和我一样在动态规划上栽过跟头希望这篇文章能让你省下几个晚上的调试时间。刷完这道题不妨立刻打开 188 题把 k 改成 3、改成 8 再写一遍亲测这样练过之后状态机真的会成为你的肌肉记忆。