“买卖股票的最好时机”系列在 LeetCode 上是一个绕不开的常客I、II、III 三道题的加起来出现频率不比反转链表低多少。很多人第一遍刷第一题时觉得很简单无非是维护一个最低价等刷到第三题“最多交易两次”就开始怀疑自己是不是根本没弄懂动态规划。我当年也一样背过题解、写过滚动数组换到第四题照样卡。直到我把 I、II、III 放在一起用同一套状态机的思路重新推了一遍才真正理解线性DP到底在干嘛。这篇文章想把我在这三道题上的实操拆解完整写出来从状态定义、转移方程到空间优化和面试讲法尽量做到“看完就能自己推出来”。1. 为什么三道“股票题”是动态规划的绝佳练手1.1 从“买卖一次”到“买卖两次”难度差在哪先看限制条件。I 说最多一次交易II 说可以无限次交易III 说最多两次交易。限制条件不同最优解的结构也完全不同这正是动态规划最吃香的地方。我最初解 I 的时候靠的是维护“历史最低价”一个循环里不断算利润模拟一下就能过。到了 II发现可以无限次买卖于是开始想“是不是每次上涨前买入、下跌前卖出”。等做到 III要求最多两次我第一反应是想办法拆区间结果怎么拆都不对劲逼得我老老实实把状态写出来才发现这几题背后的模型其实完全统一。一句话题目难度不是按代码量增长的而是按“状态数量”增长的。状态变多你对动态规划的理解就得跟着升级。这个系列也经常被面试官拿来当动态规划的敲门砖因为输入就是一维价格数组转移只依赖前一天没有图论、没有区间合并这类额外复杂度很适合考察候选人是不是真的理解状态机和转移方程而不是背了几套模板。1.2 线性DP的骨架为什么只需要关心“昨天”动态规划里有个高频词叫线性DP指的是转移方向沿着一个序列单向推进dp[i] 基本只由 dp[i-1] 推出来。股票系列就是很标准的线性DP每天结束时的最优收益只取决于前一天结束时的状态以及今天选择买、卖还是不动。拿生活场景类比你每天晚上记一笔账记录“我现在手里有没有股票账户上最多有多少钱”。第二天早上做决策时只需要参考昨晚那笔账不需要把十天前每一笔交易重新翻出来。这种只依赖上一步的性质就是所谓的无后效性。股票题目在这里做得非常纯粹没有其他干扰项所以用来建立线性DP的直觉特别合适。等你去刷洛谷的 DP 题单或者面对 Hot 100 里的其它动态规划题都会发现很多题的本质就是“盯住昨天”。我个人的感受是股票系列比 01 背包更容易让人上手。01 背包一开始要理解“选或不选”和体积守恒很多人会被二维表吓到股票系列只需要盯着“持有”和“空仓”两个概念状态少转移直观非常适合打磨动态规划的状态设计能力。2. 核心模型把“持有/不持有”设计成状态2.1 状态到底该怎么定义做动态规划最怕的就是状态定义含糊。股票系列里我建议用两个关键维度“第几天”和“手上是否持有股票”。更进一步III 还要加上“这是第几次交易”。这里有个我踩过坑的点状态描述的是“当天结束后的状态”不是“当天做过什么动作”。比如 dp[i][0] 表示第 i 天结束后空仓的最大收益dp[i][1] 表示第 i 天结束后持仓的最大收益。为什么要用“结束后的状态”因为卖出动作发生在第 i 天的某个时刻等到这一天结束你再统计时结果只有两种手上没股票或者还有股票。这样定义可以避免把“买入当天”和“卖出当天”处理得模棱两可。一开始我会忍不住把状态定义成“今天买了”或“今天卖了”结果写转移方程时处处别扭。改成“结束后的状态”之后整个推导就顺了。2.2 转移方程是怎么一步步推出来的有了状态转移方程就好写了。每天结束后你面临三个选择买入、卖出、不动。如果今天结束后空仓可能是昨天也空仓不动也可能是昨天持仓、今天卖掉了。所以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])但这里要特别提醒“通用”转移在 I 里需要微调。因为 I 最多只能买一次如果昨天空仓那么在 I 的语境下昨天空仓可能已经完成了一次交易今天再买就是第二次交易不合法。所以 I 的持仓状态只能来自“之前从未买过”加“今天买入”dp[i][1] max(dp[i-1][1], -prices[i])这个细节直接区分你是否真正理解了 I 和 II 的本质差异。II 无限次交易昨天空仓今天就能再买用完整转移式I 限制一次交易买入动作只能发生一次。很多实现题解看起来差不多实际这里已经在变化了。III 则是在 I/II 的基础上引入“第几次”的维度转移依然是一条线推过去。先不要被四个状态吓到本质上就是“第一次持仓、第一次空仓、第二次持仓、第二次空仓”四个节点顺序推进。2.3 初始化为什么是这些东西第一天没有“昨天”所以必须手动给边界。第一天结束后如果空仓收益是 0如果持仓相当于当天买入收益是 -prices[0]。我见过不少人在 III 的初始化上栽跟头。III 要开四个状态第一次持仓初始化为 -prices[0]第二次持仓也初始化为 -prices[0]。看似离谱但逻辑上说得通第一天先买入再卖出利润 0再买入仍然花费 prices[0]。虽然同一天买卖没有实际意义但这样初始化让第二次买入有机会从第一天开始不会漏掉任何解。第一次空仓和第二次空仓都初始化为 0。这些初始化值看起来是细节实际上定错一个后面全错。宁可多花五分钟验证边界也不要盲目跟着模板抄。3. 三道题放在一起一眼看清复杂度的差异3.1 从暴力枚举到动态规划复杂度降了多少很多没系统学过 DP 的人第一反应是枚举所有交易区间。第一题两层循环枚举买入日和卖出日O(n^2)第二题无限次交易要枚举所有交易组合指数级第三题两次交易如果枚举两个交易区间理论上直接 O(n^4)。动态规划把复杂度压到 O(n)是一个非常典型的“用状态换时间”的过程。每天只保留前一天的状态然后通过 max 决策推进相当于把你不需要的信息全部丢掉。也许有人觉得 O(n) 也没多厉害但 n 一旦到十万级别O(n^2) 就是 100 亿次操作跑起来会很吃力O(n) 则毫无压力。题目暴力复杂度状态数DP复杂度IO(n^2)n * 2O(n)II指数级n * 2O(n)IIIO(n^4)n * 4O(n)这三道题放在一起能很直观看出动态规划的核心收益不是让代码变短而是让时间复杂度从不可接受变成可接受。3.2 三道题的状态维度和结果取值对照把三道题的状态维度放在一起I 和 II 的状态数都是两个但转移不同III 是四个状态。结果取值的差异也值得注意I 和 II 直接返回 dp[-1][0]也就是最后一天空仓的最大收益III 则要取第一次空仓、第二次空仓和 0 三者的最大值。题号限制条件状态含义最终返回I最多 1 次交易空仓 / 持仓dp[-1][0]II无限次交易空仓 / 持仓dp[-1][0]III最多 2 次交易第一次空仓/持仓、第二次空仓/持仓max(第一次空仓, 第二次空仓, 0)为什么 I 和 II 的状态数一样代码却不同因为 I 的持仓状态只能来自“未交易过的空仓”II 的持仓状态可以来自“已经做过若干次交易后的空仓”。这就是状态数相同、转移方程不同导致最优解结构完全改变的例子。4. I、II、III 逐题拆解从二维DP到一维滚动4.1 买卖股票的最佳时机 I先写DP再谈优化第一题最简单但我也坚持用状态机框架来写这样后续题目才能统一。下面这份代码是标准二维表版本帮助你理解结构def max_profit_i(prices: list[int]) - int: if not prices or len(prices) 2: return 0 dp [[0, 0] for _ in range(len(prices))] dp[0][0] 0 dp[0][1] -prices[0] for i in range(1, len(prices)): dp[i][0] max(dp[i - 1][0], dp[i - 1][1] prices[i]) dp[i][1] max(dp[i - 1][1], -prices[i]) return dp[-1][0]注意 dp[i][1] 用的是 -prices[i]而不是 dp[i-1][0] - prices[i]。原因前面说了I 只允许一次买入。这里的 -prices[i] 可以理解成“手里现金为 -prices[i]”也就是之前没有累积收益直接买入。当然第一题有更简练的写法维护一个历史最低价不断更新利润def max_profit_i_fast(prices: list[int]) - int: min_price prices[0] ans 0 for price in prices[1:]: ans max(ans, price - min_price) min_price min(min_price, price) return ans面试时如果先写了双变量版本我通常补一句“这其实可以看作滚动数组压缩后的 DP”。面试官一般都会认可这种理解深度。4.2 买卖股票的最佳时机 II交易次数不受限制II 允许无限次交易转移方程回到完整版def max_profit_ii(prices: list[int]) - int: if not prices or len(prices) 2: return 0 dp [[0, 0] for _ in range(len(prices))] dp[0][0] 0 dp[0][1] -prices[0] for i in range(1, len(prices)): 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]) return dp[-1][0]观察持仓状态dp[i][1] 现在可以从 dp[i-1][0] - prices[i] 转移过来说明卖出后赚到的钱可以立刻用来买下一次股票这正是无限次交易的核心。因为允许无限交易这道题还可以用贪心做只要今天比昨天贵就认为这段利润可赚把所有正差价累加。但贪心没有 DP 的通用性一旦加了交易次数限制就失效所以我还是建议用 DP 框架把它统一起来。def max_profit_ii_greedy(prices: list[int]) - int: ans 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: ans prices[i] - prices[i - 1] return ans贪心版本只有几行很多人刷完就跑了忙不迭进入下一题。但如果你想建立起“一套框架解决一个系列”的能力DP 版本必须写一遍否则到了 III 会断档。4.3 买卖股票的最佳时机 III四个状态硬刚“最多两次”第三题需要把状态拆成四份第一次买入后仍持仓第一次持有第一次卖出后空仓第一次不持有第二次买入后持仓第二次持有第二次卖出后空仓第二次不持有转移关系是一步一步推进的没有持仓 - 第一次持仓 - 第一次空仓 - 第二次持仓 - 第二次空仓。听起来绕但代码其实很对称def max_profit_iii(prices: list[int]) - int: if not prices or len(prices) 2: return 0 dp [[0] * 4 for _ in range(len(prices))] dp[0][0] -prices[0] dp[0][2] -prices[0] for i in range(1, len(prices)): dp[i][0] max(dp[i - 1][0], -prices[i]) dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i]) dp[i][2] max(dp[i - 1][2], dp[i - 1][1] - prices[i]) dp[i][3] max(dp[i - 1][3], dp[i - 1][2] prices[i]) return max(dp[-1][1], dp[-1][3], 0)建议把每个转移方程读成一句人话第一次持仓要么昨天已经持仓不动要么今天完成第一次买入。第一次空仓要么昨天已经空仓要么昨天第一次持仓、今天卖掉。第二次持仓要么昨天已经是第二次持仓要么昨天第一次空仓、今天再次买入。第二次空仓要么昨天已经空仓要么昨天第二次持仓、今天卖掉。最后返回时取三个值 max。有人会问为什么不直接返回 dp[-1][3]因为最优解可能只做了一次交易。当只做一次交易更优时第二次卖出状态可能等于第一次卖出状态也可能被不合理的操作拉低。保守写法就是三个值取 max稳。4.4 空间优化从二维数组到四个滚动变量之所以说这些题适合入门还有一个重要原因状态只依赖相邻一天所以可以压缩空间。III 完全可以只用四个变量滚动更新。但这里需要认真讲清楚我已经见过不少人在这一步写出错误答案。先说正确版本def max_profit_iii_roll(prices: list[int]) - int: if not prices or len(prices) 2: return 0 s0, s1, s2, s3 -prices[0], 0, -prices[0], 0 for price in prices[1:]: ns0 max(s0, -price) ns1 max(s1, s0 price) ns2 max(s2, s1 - price) ns3 max(s3, s2 price) s0, s1, s2, s3 ns0, ns1, ns2, ns3 return max(s1, s3, 0)这里有个小陷阱ns2 要用的 s1 是“上一次循环结束后的 s1”不是本轮新算的 ns1。所以我用 ns 开头的一组临时变量等到四个新值全部算完再统一赋值。如果你图省事直接原地逐个更新就很容易把刚算出来的新值又用进去结果全部错乱。如果不想用临时变量另一个方案是从后往前更新先算 s3再算 s2、s1、s0因为 s3 用的是旧 s2s2 用的是旧 s1顺序反过来时每个旧值还没有被覆盖。我自己的习惯是依赖旧值i-1的多变量 DP要么用临时变量要么从后往前更新绝不原地正向胡乱覆盖。这条习惯救了我很多次。5. 高频翻车点排查与实战建议5.1 别拿“两次第一题”硬解第三题我第一次试图解 III 时想的是先找一次利润最大的交易删除再在剩余区间找第二次交易。结果遇到[5, 0, 6, 2, 7]直接翻车。跑一次 I 会找到 0 买入、7 卖出利润 7剩余区间根本凑不出第二笔有效交易所以总利润是 7。但真正的最优解是 0 买入、6 卖出赚 6再 2 买入、7 卖出赚 5总利润 11。两次交易之间存在“相互挤压”第一次交易选了最大的单段利润反而把后面两段高利润区间一起毁了。状态机 DP 之所以能赢就是因为它同时维护“第一次交易进行到哪、第二次交易进行到哪”的组合而不是先定死一笔交易再去找另一笔。不过如果你真的想用“两次 I”的思路解 III正确姿势是枚举分割点分别计算左侧一次交易的最大利润和右侧一次交易的最大利润再求和取最大这是可以的。要注意区分“枚举分割点”和“先全局找一次最优再剔除”的区别后者不是正确做法。5.2 贪心在II里能用别高兴太早II 的贪心解法很舒服遇到prices[i] prices[i-1]就累加差值。但你要知道它为什么能成立因为不限交易次数任意一段连续上涨都可以被拆成多个相邻利润不会存在“合并后更优”的情况。而一旦限制交易次数贪心就失灵。I 限制一次必须拿到波峰到波谷的最大单次差值III 限制两次还要考虑两笔交易的配合。这时候只能回到动态规划。我在面试时如果写了贪心一定会主动说一句“如果改成最多 k 次交易我就得用状态机 DP。”这句话往往比代码本身更能体现你的算法视野。5.3 边界条件与答案取值速查表把容易踩的点整理成一张速查表刷题前扫一眼能省很多时间场景正确做法说错就翻车的点prices 为空直接返回 0访问 prices[0] 报错第一天初始化持仓对应 -prices[0]误写成 0后续成本少算III 的第二次持仓初始值-prices[0]误写成 0可能漏掉第一天就建仓第二次的情况III 最终返回max(第一次空仓, 第二次空仓, 0)只取第二次空仓可能丢掉“最优解只有一次交易”的情况滚动更新临时变量或逆序更新新旧值混算答案乱掉还有一个细节只要价格序列长度小于 2必然无法完成任何盈利交易直接返回 0。写题时不要只判断not prices也要看看len(prices) 1的情况。当然你也可以统一在最前面处理if len(prices) 2: return 0这样更稳。5.4 遇到“最多k次交易”第四题怎么迁移III 做完之后最自然的追问就是“如果最多 k 次交易呢”也就是股票系列第四题。其实你把 III 的四个状态扩展成 2k 个状态每个交易次数对应“持仓/空仓”两态转移逻辑完全一样。这也是我推荐用状态机模型学习股票系列的原因它可以一路平滑延伸到更难的变体。与其死记每一题的代码不如把“状态定义、初始化、转移方向”这个三角拆干净。面试官问的时候你能五分钟把状态方程写出来并讲清楚每一个 max 在比较什么比背十遍代码都管用。写在最后的实战心得拿到任何动态规划题先问自己三句——状态是什么、初始化在哪、转移依赖谁。股票系列刚好把这三句练到极致。我第一次写 III 的滚动数组时就是因为没保存旧状态翻过车后来强制自己用临时变量兜底才真正形成肌肉记忆。如果你正在刷 Hot 100或者在洛谷的 DP 题单里打转我建议把这三道题连在一起做一遍从二维表写到一维滚动再顺手推到第四题。等下次再遇到状态机味道的新题你会比现在从容很多。