企业官网建设流程全解析

“买卖股票的最好时机”系列在 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) 则毫无压力。

这三道题放在一起，能很直观看出动态规划的核心收益：不是让代码变短，而是让时间复杂度从不可接受变成可接受。

3.2 三道题的状态维度和结果取值对照

把三道题的状态维度放在一起，I 和 II 的状态数都是两个，但转移不同；III 是四个状态。结果取值的差异也值得注意，I 和 II 直接返回 dp[-1][0]，也就是最后一天空仓的最大收益；III 则要取第一次空仓、第二次空仓和 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 用的是旧 s2，s2 用的是旧 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 边界条件与答案取值速查表

把容易踩的点整理成一张速查表，刷题前扫一眼能省很多时间：

还有一个细节：只要价格序列长度小于 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 题单里打转，我建议把这三道题连在一起做一遍，从二维表写到一维滚动，再顺手推到第四题。等下次再遇到状态机味道的新题，你会比现在从容很多。