企业官网建设流程全解析

如果你的动态规划学习进度已经走到第30天，大概率会在一个系列题目上停下来死磕：买卖股票。这套题从LeetCode 121一直排到714，横跨六七个编号，故事背景全是“给定一个价格数组，算最大利润”，但解法却一层比一层绕。很多人从01背包、最少硬币问题一路刷过来，到了股票题突然蒙住，原因很简单——前一类问题是在“选/不选”做决策，股票题却引入了“持有/不持有”这种跟时间绑定的状态，思维模型不一样了。

这篇文章不打算做那种只贴代码的题解汇总，我想把Day30这一天我真正想明白的东西完整写出来：为什么买卖股票是状态机DP的最佳入门、六道题之间是怎么一层层叠加约束的、每一道题的转移方程怎么从0推出来、以及我在刷题时踩过哪些坑。内容适合准备面试的选手，也适合正在用动态规划入门、想彻底搞懂状态转移的新手。

1. 写在Day30：这套股票题到底在考什么

1.1 六道股票题一张表看懂递进关系

很多人第一次见到“买卖股票”系列，会觉得题长得一模一样：给一个数组 prices，prices[i] 表示第 i 天的价格，你可以在某些天买入、某些天卖出，返回最大利润。唯一的区别藏在小字里，而且每一道题的限制都不一样：

我刷完这六道题之后最大的感受是：它们不是六个独立问题，而是一套同一个模型的渐进式变体。如果你只背每一道题的解法，永远会忘；如果你先搞懂那个统一的状态机模型，这六道题其实只要花一晚上就能全部推导出来。

1.2 为什么股票题值得作为DP进阶的重要节点

我推荐的动态规划刷题路径通常是：先搞定斐波那契、爬楼梯这类线性DP，然后是01背包、完全背包这类组合优化，接着就到了股票系列。前两类问题能让你理解“子问题”和“状态转移”，但股票系列才是真正把状态机思想引入DP的关键转折点。

01背包和最少硬币问题里，每个物品只有“选”和“不选”，你关注的维度主要是容量。股票题完全不同：你在每一天都有“持有”和“不持有”两种状态，而且这种状态是可以互相转换的——买入让你从不持有变成持有，卖出让你从持有变成不持有。这就是典型的有限状态机。理解了这个模型，后面很多复杂DP——比如打家劫舍、编辑距离、区间DP——思考方式都会顺很多。

2. 核心思路：所有股票题都能统一成状态机模型

2.1 状态设计的两层维度：持股状态与交易次数

想明白股票题，第一件事是忘掉“今天是第几天”之外的所有直觉，只留下两个问题：第一，今天操作完之后，手里还有没有股票？第二，到目前为止已经完成了多少笔交易？

第一个问题的答案只有两种：有股票，或者没股票。有些人叫它“持有”和“空仓”，你甚至可以把它理解为手里拿着一个仓库的钥匙，买入等于把钥匙拿在手上，卖出等于把钥匙交出去。没有别的中间状态，这就叫状态枚举完整。

第二个问题出现在限制了交易次数的题目里（123、188）。你总共只能买卖 k 次，那么当前这个时刻已经用掉了多少次，必须记下来。这个维度在123题里是0、1、2三档，在188题里是0到k一共k+1档。

所以我习惯把股票题DP数组定义成这样的统一形式：

dp[i][k][0] # 第 i 天结束，已经至多完成 k 笔交易，手里没有股票，最大利润 dp[i][k][1] # 第 i 天结束，已经至多完成 k 笔交易，手里有股票，最大利润

[0] 和 [1] 就是手里有没有货这个状态维度，k 是交易次数维度，i 是时间维度。几乎所有股票题都能套进这个框架，区别只在于k的范围、交易次数在哪一步消耗、以及有没有额外的冷冻期或者手续费。

2.2 交易次数到底在哪一步加一

这个细节是我初期最混乱的地方，也是网上题解经常不统一的地方。有人规定“买入时算消耗一次交易”，有人规定“卖出时算完成一次交易”，两种写法都能做对，但如果你混着看不同博主的代码，就很容易算晕。

我最终选择了“买入时消耗一次交易”这个约定，并且固定下来不再变。理由是：一次完整的买卖包括买入和卖出，把它看成买入时开了一张新交易的凭证，卖出只是这张凭证的兑现，逻辑上更顺。对应到转移方程里：

• 今天买入：从昨天的“已用 k-1 次交易、无股票”状态，减去今天的价格，变成“已用 k 次交易、有股票”
• 今天卖出：从昨天的“已用 k 次交易、有股票”状态，加上今天的价格，变成“已用 k 次交易、无股票”

这个约定一旦固定，写代码几乎不会出边界错误，因为k的消耗位置非常明确。我强烈建议你也选一个约定，然后所有股票题都用同一个，别今天用买入消耗明天用卖出消耗。

2.3 从两个状态到三个状态：状态集合的“显式化”

到了309题，题目多了一个条件：卖出股票后的第二天不能买入，也就是冷冻期。这个约束的本质是什么？是“不持股”这个状态内部出现了分叉：你可能处于“卖出了正在冷冻”，也可能处于“没有股票而且随时可以买”。

那怎么办？把状态集合拆开，从2个变成3个。这种思路在DP里很常见：当一个状态内部行为不一致时，就把它拆成更细的状态。后面714题的“手续费”则更简单，它不需要新增状态，只是在卖出时把手续费从利润里扣掉就完了。

我之所以强调这个递进，是因为很多刷题的人到了309会突然卡住。其实用“状态机”视角看，冷冻期只是给“不持有”这个状态加了细分，不是全新的模型。模型没变，变的只是状态数量。

3. 实操过程：从121到714，一步一步把代码写出来

3.1 121题：只买卖一次，先学维护历史最低点

121是最温和的一道题。虽然它也可以用状态机模板解，但最优解其实只需要一个变量，反而能帮你建立对“一次交易”的直觉。

思路是这样的：如果你只能买卖一次，那你在第 i 天卖出的最大利润，一定等于 prices[i] 减去前 i-1 天里的最低价格。所以我只要在遍历数组的同时维护一个 min_price 变量记录当前遇到的最低价格，再用当前价格减去 min_price，更新最大利润。

def max_profit(prices): min_price = float('inf') max_profit = 0 for price in prices: min_price = min(min_price, price) max_profit = max(max_profit, price - min_price) return max_profit

这个解法的时间复杂度 O(n)，空间复杂度 O(1)。注意 min_price 初始值一定要设为无穷大，不能设成 prices[0] 以外的数字，否则可能出现第一次比较就出错。还有一种写法是用“连续子数组最大和”的思路，把每天的价格差当成数组元素，但这需要额外构造差值数组，没必要。

从状态机的角度看，121其实是在说：最多交易一次，所以你在卖出前最多只能有一次买入。它的状态维数太浅，反而不适合作为学习状态机的入口，更适合作为热身。

3.2 122题：不限次数，状态机DP第一次登场

122题把限制放宽成“可以无限次买卖”，但不能同一天既买又卖。这道题我第一次看到时第一反应是贪心：只要明天的价格比今天高，就今天买入明天卖出。确实，贪心一趟循环就能过，代码还特别短。

但如果你想为后面123、188打基础，我建议这题还是老老实实用状态机DP来解。状态只有两个：

• dp0：当前不持有股票的最大利润
• dp1：当前持有股票的最大利润

每一天的状态只有两种情况：继续维持原状态，或者从另一个状态转换过来。今天不持有，要么昨天也不持有，要么昨天持有且今天卖出；今天持有，要么昨天也持有，要么昨天不持有且今天买入。

def max_profit(prices): dp0 = 0 dp1 = -prices[0] for price in prices[1:]: new_dp0 = max(dp0, dp1 + price) new_dp1 = max(dp1, dp0 - price) dp0, dp1 = new_dp0, new_dp1 return dp0

注意这里用了一个小技巧：在计算 new_dp1 时用的是更新前的 dp0，也就是“昨天不持有”的利润，而不是“今天不持有”的利润。因为同一天不能先卖后买，如果你直接用更新后的 dp0 去计算买入，等于允许了同日卖出再买入，虽然这道题结果可能碰巧一致，但到了带冷冻期的题目就会出错。所以我用临时变量 new_dp0、new_dp1 再一起覆盖，养成这个习惯后面会省很多事。

3.3 123题：最多两笔，状态数量第一次膨胀

123题把限制改成“最多交易两笔”。这时候状态必须加上交易次数维度。我直接用 k=2 的通用模板来写，因为这样到了188题只需要把2换成k：

def max_profit(prices): n = len(prices) if n == 0: return 0 dp = [[0] * 2 for _ in range(3)] dp[0][1] = float('-inf') dp[1][1] = -prices[0] dp[2][1] = -prices[0] for price in prices[1:]: for k in range(1, 3): dp[k][0] = max(dp[k][0], dp[k][1] + price) dp[k][1] = max(dp[k][1], dp[k-1][0] - price) return max(dp[0][0], dp[1][0], dp[2][0])

这段代码里最需要注意的就是 dp[0][1] = float('-inf')。含义是：一次交易都不允许完成的情况下，你不可能持有股票，这个状态必须是一个极小值，而不是0。如果你把它初始化为0，转移时它可能会被当成“合法状态”参与买入计算，导致结果偏大。

为什么 dp[1][1] 和 dp[2][1] 都初始化为 -prices[0]？因为第一天你只有两种选择：不买，利润0；买入，利润变成负的第一天价格。不管之后限制是1笔还是2笔，第一天买入后的持有状态都是一样的，都消耗了一次交易次数。这里的边界处理是整个题目的关键，后面188题也是同样的逻辑。

3.4 188题：把2推广成k，顺便解决超大k的退化问题

188是123的泛化，限制从“最多2笔”变成“最多k笔”。如果直接套模板，就是三维数组的写法，但空间复杂度会变成O(k * n)，还可以继续优化成O(k)：

def max_profit(k, prices): n = len(prices) if n == 0 or k == 0: return 0 if k > n // 2: profit = 0 for i in range(1, n): if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] return profit dp = [[0] * 2 for _ in range(k + 1)] for i in range(1, k + 1): dp[i][1] = -prices[0] for price in prices[1:]: for i in range(1, k + 1): dp[i][0] = max(dp[i][0], dp[i][1] + price) dp[i][1] = max(dp[i][1], dp[i-1][0] - price) return dp[k][0]

这里有两个点非常值得展开。第一，为什么当 k > n // 2 时可以直接退化成贪心？因为一次交易至少需要两天，n天里最多完成 n/2 笔“不相交”的买卖。如果题目给的k已经超过这个上限，实际上等价于不限制交易次数，用122的贪心或者状态机都行。这个优化不只是亮点，还能防止创建过大数组导致的性能问题。

第二，循环顺序为什么必须从1到k从小到大？因为 dp[i][1] 依赖的是 dp[i-1][0]（更小的交易次数），而 dp[i][0] 依赖 dp[i][1]（当前交易次数）。在这个二维数组的空间压缩里，不存在01背包那样“从大到小遍历”的必要，因为这里没有对同一个i的覆盖问题。但如果你压缩成一维数组后写错了顺序，结果会非常诡异，我在后面第4章还会细说。

3.5 309和714：冷冻期与手续费，状态机的两种变体

309题引入冷冻期，卖出股票后的第二天不能买入。状态从2个拆成3个：

• dp0：不持股，且不在冷冻期（可以自由买入）
• dp1：不持股，且处于冷冻期（刚卖出）
• dp2：持股

转移关系是：今天处于冷冻期，说明昨天一定卖了股票；今天不持股且不冷冻，说明昨天要么也不持股且不冷冻，要么昨天刚结束冷冻期；今天持股，说明昨天要么也持股，要么昨天不持股且不冷冻并买入。

def max_profit(prices): n = len(prices) if n == 0: return 0 dp0, dp1, dp2 = 0, float('-inf'), -prices[0] for price in prices[1:]: new_dp0 = max(dp0, dp1) new_dp1 = dp2 + price new_dp2 = max(dp2, dp0 - price) dp0, dp1, dp2 = new_dp0, new_dp1, new_dp2 return max(dp0, dp1)

写这题时我第一次犯的错误是把 dp1 初始化为0。仔细想一下就明白：第一天不可能“刚卖出股票”，所以这个状态必须初始化为负无穷，否则买入逻辑会被污染。这类“非法状态用负无穷”的处理，是股票系列最常见的考察点，几乎每一道题都会遇到。

714题就友好多了，只加了一个手续费。我们约定手续费在卖出时扣除，所有转移逻辑跟122一模一样，唯一的区别是卖出利润要减掉 fee：

def max_profit(prices, fee): dp0 = 0 dp1 = -prices[0] for price in prices[1:]: new_dp0 = max(dp0, dp1 + price - fee) new_dp1 = max(dp1, dp0 - price) dp0, dp1 = new_dp0, new_dp1 return dp0

需要注意手续费扣除的时机。如果把手续费放在买入时扣，利润结果一样，但一旦题目把冷冻期加进来，不同时机会影响状态转移，所以最好固定为“卖出时扣”并形成肌肉记忆。

4. 实战中反复踩的坑：初始化、边界与调试方法

4.1 非法状态为什么要用负无穷

股票DP里最常见的错误就是“非法状态参与转移”。什么算非法状态？比如一次交易都没完成却持有股票，或者冷凍期内还买入。这些状态在现实里不可能出现，但在DP表里如果没有被初始化成负无穷，会被默认当成0参与max比较，导致结果偏大。

判断一个状态是否非法，我的技巧是：从第0天顺着时间线推，看能否通过合法的买入卖出到达它。如果答案是不能，那它就必须是负无穷。例如121题不需要这个处理，因为变量只存利润；但123题的 dp[0][1] 明显非法，所以必须设为负无穷。

4.2 空间压缩后的循环顺序怎么判断

股票系列里最容易写出“表面正确但答案错”的代码，就是空间压缩后的循环顺序问题。188题用二维dp[k][2]时，外层遍历天数、内层遍历交易次数，顺序很明确。但如果你想再压缩成一维数组，就要考虑：dp[i][1] 使用前一天的 dp[i-1][0]，如果i从小到大遍历，dp[i-1][0]在本轮已经先被更新过，就会串味。

我的经验是：但凡拿不准顺序，就不要强行压缩。先写二维数组，过了样例再考虑优化。面试时候没人会因为你用O(kn)空间挂你，但如果你因为压缩写错导致样例都跑不过，那才是真的扣分。

4.3 调试股票DP的独门技巧

遇到答案不对，我的排查步骤永远是固定的。第一步，找一个只有三四天的简单用例，把每天的dp表完整打印出来，手动推一遍转移，看哪天开始出现离谱值。第二步，检查初始化：把每个dp维度的初始值列成表，逐个问“这个状态在第0天合法吗”。第三步，检查交易次数消耗位置：随便找一组数据，按照你设定的买入/卖出流程手算一遍，对比代码中k值的变化。

打印dp表时，我还会特意打印“交易次数”这个维度，因为在123和188里，最容易出错的不是状态值本身，而是k的迁移。我见过不少人代码写错是因为在更新 dp[k][1] 时用了 dp[k][0] 而不是 dp[k-1][0]，这种错误光看公式很难发现，但一打印dp表立刻现形。

4.4 一套可以直接套用的思考模板

刷完整套股票题，我给自己总结了一套面试时快速破题的模板，分享出来供参考。看到股票题，先问四个问题：第一，最多能交易几次？一次、两次、无限次、还是给定的k次？第二，有没有冷冻期？第三，有没有手续费？第四，是否限制同一天买卖？

第一个问题决定要不要加“交易次数”维度，第二个问题决定“不持股”状态要不要拆成两个，第三个问题决定转移方程里要不要加减常数，第四个问题决定临时变量更新顺序。把四个问题快速过一遍，状态定义和转移方程基本就定了。这个模板我用在面试里屡试不爽，因为面试官问股票题，考察的往往不是你能不能背出代码，而是你能不能通过约束变化举一反三。

5. 收尾：学完这组题我的一些体会

刷到Day30这个节点，我对动态规划的理解跟第1天完全不一样了。最开始我觉得DP就是找递推公式，套公式做题；直到股票系列让我意识到，状态的定义比转移公式本身重要得多。一个状态定义得清楚，转移是水到渠成的事情；状态定义模糊，背下公式也没有输出能力。

这六道题最强的价值在于，它逼着你去思考“除了价值和容量，还要记录哪些附加信息”。交易次数、冷冻期、手续费，每个约束都对应状态维度的增加或者转移成本的调整。到了后面你做编辑距离、正则匹配这类经典DP题时，这套“先枚举状态，再写转移，最后补边界”的流程完全一致。

最后再分享一个小技巧：刷股票系列时，不是把所有解法都记住才算会。我最推荐的方式是把122题那个两状态转移当成基本功练熟，然后每遇到一道新题，先不查题解，用“状态拆分四问”推一次状态定义，再自己写转移。推不出来的地方，才是你需要记录的重点。这套方法帮我从“背题人”变成了“解题人”，也希望能帮到你。