从状态机DP视角彻底搞懂买卖股票系列（LeetCode 121到714）-北京尧图网络

如果你的动态规划学习进度已经走到第30天大概率会在一个系列题目上停下来死磕买卖股票。这套题从LeetCode 121一直排到714横跨六七个编号故事背景全是“给定一个价格数组算最大利润”但解法却一层比一层绕。很多人从01背包、最少硬币问题一路刷过来到了股票题突然蒙住原因很简单——前一类问题是在“选/不选”做决策股票题却引入了“持有/不持有”这种跟时间绑定的状态思维模型不一样了。这篇文章不打算做那种只贴代码的题解汇总我想把Day30这一天我真正想明白的东西完整写出来为什么买卖股票是状态机DP的最佳入门、六道题之间是怎么一层层叠加约束的、每一道题的转移方程怎么从0推出来、以及我在刷题时踩过哪些坑。内容适合准备面试的选手也适合正在用动态规划入门、想彻底搞懂状态转移的新手。1. 写在Day30这套股票题到底在考什么1.1 六道股票题一张表看懂递进关系很多人第一次见到“买卖股票”系列会觉得题长得一模一样给一个数组 pricesprices[i] 表示第 i 天的价格你可以在某些天买入、某些天卖出返回最大利润。唯一的区别藏在小字里而且每一道题的限制都不一样题号限制条件核心考点状态数量121只能买卖一次一维DP / 贪心思想1个变量122可以买卖无限次状态机DP入门2个状态123最多买卖两次状态机升级4个状态188最多买卖 k 次通用状态机 / 空间压缩2k个状态309卖出后有一天的冷冻期状态集合拆分3个状态714每次交易有手续费转移时加成本2个状态我刷完这六道题之后最大的感受是它们不是六个独立问题而是一套同一个模型的渐进式变体。如果你只背每一道题的解法永远会忘如果你先搞懂那个统一的状态机模型这六道题其实只要花一晚上就能全部推导出来。1.2 为什么股票题值得作为DP进阶的重要节点我推荐的动态规划刷题路径通常是先搞定斐波那契、爬楼梯这类线性DP然后是01背包、完全背包这类组合优化接着就到了股票系列。前两类问题能让你理解“子问题”和“状态转移”但股票系列才是真正把状态机思想引入DP的关键转折点。01背包和最少硬币问题里每个物品只有“选”和“不选”你关注的维度主要是容量。股票题完全不同你在每一天都有“持有”和“不持有”两种状态而且这种状态是可以互相转换的——买入让你从不持有变成持有卖出让你从持有变成不持有。这就是典型的有限状态机。理解了这个模型后面很多复杂DP——比如打家劫舍、编辑距离、区间DP——思考方式都会顺很多。2. 核心思路所有股票题都能统一成状态机模型2.1 状态设计的两层维度持股状态与交易次数想明白股票题第一件事是忘掉“今天是第几天”之外的所有直觉只留下两个问题第一今天操作完之后手里还有没有股票第二到目前为止已经完成了多少笔交易第一个问题的答案只有两种有股票或者没股票。有些人叫它“持有”和“空仓”你甚至可以把它理解为手里拿着一个仓库的钥匙买入等于把钥匙拿在手上卖出等于把钥匙交出去。没有别的中间状态这就叫状态枚举完整。第二个问题出现在限制了交易次数的题目里123、188。你总共只能买卖 k 次那么当前这个时刻已经用掉了多少次必须记下来。这个维度在123题里是0、1、2三档在188题里是0到k一共k1档。所以我习惯把股票题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题把限制改成“最多交易两笔”。这时候状态必须加上交易次数维度。我直接用 k2 的通用模板来写因为这样到了188题只需要把2换成kdef 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一模一样唯一的区别是卖出利润要减掉 feedef 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题那个两状态转移当成基本功练熟然后每遇到一道新题先不查题解用“状态拆分四问”推一次状态定义再自己写转移。推不出来的地方才是你需要记录的重点。这套方法帮我从“背题人”变成了“解题人”也希望能帮到你。

从状态机DP视角彻底搞懂买卖股票系列（LeetCode 121到714）

相关推荐

大模型代理合作与聚合平台：从技术原理到落地实战全解析

git remote prune：清理过期远程跟踪分支，解决仓库迁移后push失败

模式识别三层决策逻辑：不确定性建模、判别结构与优化求解

更多资讯

堆内存分代调优：新生代与老年代的比例调整（含性能测试）

YourKit Java Profiler：高级性能分析工具使用教程（附案例）

流放之路2 Build规划工具Path of Building 2：完整离线构建规划指南

Windows Defender 禁用修复完全指南：用 no-defender 后 4 步恢复 Windows 安全中心

tiny11builder 指南：5 步把官方 Windows 11 ISO 精简成可启动镜像

echarts-2.2.7离线内网部署与IE8兼容避坑指南

今日更新

Verilog实现FPGA密码锁：矩阵键盘与状态机设计实战

数据服务监控运维实战：从指标体系到告警治理与故障排查

FreeRTOS任务通知实战详解：内核原理、API与避坑指南

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？