第41天刷到“买卖股票”这一组算是动态规划里非常经典的一条递进线了。121、122、123三题放在一起表面都是股票买卖实际是在练同一种能力把“交易次数”和“是否持仓”抽象成状态再通过状态之间的转移来建模整个过程。很多人刷股票题容易卡住根源往往不是看不懂题而是没想明白“状态”到底代表什么以及为什么有时候能贪心、有时候必须动态规划。这篇文章我把这三道题串在一起讲从最简单的单次交易开始逐步升级到无限次交易、最多两笔交易把我自己在做题时踩过的坑、总结出来的规律、以及初始化时的一些反直觉细节都写清楚。适合刚开始刷股票系列、或者刷了但总觉得状态转移有点“背公式”的同学参考。1. 为什么把三道股票买卖题放在同一天刷1.1 三个问题的递进关系121、122、123是同一个故事模板的三个变体给定一只股票每天的价格数组计算最大利润。121只能买卖一次。122可以买卖任意多次但任何时候最多持有一股。123最多买卖两次也就是最多两笔完整交易。这三题放在一起刷价值在于它们共享同一套“状态机”思维。121是所有股票DP的雏形122是在121基础上放开交易次数限制123则是把交易次数从无限次收紧到有限次。三题各改一个条件解法就从“一维变量”变到“二维DP”再变到“多维状态DP”非常适合用来理解动态规划里的状态设计。先说结论这三题都能用动态规划解决而且能用一套几乎相同的状态转移逻辑。区别只在“买入时的现金要基于什么状态计算”。搞懂这个区别三题就一次性打通了。1.2 为什么不用暴力或贪心121可以用一个变量记录历史最低价复杂度O(n)很多资料称它为“一次遍历法”严格来说它不算DP但是思路非常接近DP的滚动变量版。122有贪心解只要价格比前一天高就累加差值。这个解很简洁但贪心成立的原因是“允许无限次交易”且“无手续费”所以每一个正差价都可以独立收割。一旦交易次数受限比如123贪心立刻失效。你没法只靠“今天涨了就卖”来保证“最多两笔交易”下的全局最优因为今天卖了可能就没机会再买回最优区间。123显然需要真正意义上的DP。你需要显式地记录“我已经完成了多少笔交易”“当前是否持仓”这两类信息。所以从121到123本质是把“能不能贪心”和“要不要DP”这个问题也顺带想明白了。2. 121. 买卖股票的最佳时机单次交易的DP起点2.1 状态怎么定只买卖一次意味着整个过程只需要关心两个阶段买入前、持有中。很多人习惯直接用变量写法def maxProfit(prices): min_price prices[0] profit 0 for p in prices[1:]: profit max(profit, p - min_price) min_price min(min_price, p) return profit这个写法很好也很容易理解。但为了和122、123统一最好先看它的DP版本。我定义两个状态dp[i][0]第i天结束时手里持有股票时账户上的最大现金余额。dp[i][1]第i天结束时手里不持有股票时账户上的最大现金余额。这里的“现金余额”是一个虚拟变量初始资金视作0。你买入股票现金余额变成负数卖出股票现金余额增加。2.2 转移关系的推导对于持有状态dp[i][0]它有两个来源前一天就已经持有今天继续拿着dp[i-1][0]今天才买入因为只允许一次交易买入前的现金一定是初始资金0所以买入后现金是-prices[i]所以dp[i][0] max(dp[i-1][0], -prices[i])这里要注意买入时不能用dp[i-1][1] - prices[i]因为如果用了这个式子意味着买之前可能已经卖出过一次那就不满足“只买卖一次”了。这是121和122最核心的区别。对于不持有状态dp[i][1]也有两个来源前一天就不持有今天继续观望dp[i-1][1]前一天还持有今天卖出dp[i-1][0] prices[i]所以dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i])初始化时dp[0][0] -prices[0] dp[0][1] 0最后答案就是dp[-1][1]也就是最后一天不持有股票时的最大现金。2.3 代码实现与空间优化完整写法def maxProfit(prices): n len(prices) if n 2: return 0 dp [[0, 0] for _ in range(n)] dp[0][0] -prices[0] dp[0][1] 0 for i in range(1, n): dp[i][0] max(dp[i - 1][0], -prices[i]) dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i]) return dp[-1][1]由于第i天只依赖第i-1天完全可以压缩成两个变量def maxProfit(prices): n len(prices) if n 2: return 0 hold -prices[0] cash 0 for p in prices[1:]: # 这里必须用旧值计算所以先算cash再算hold或者用临时变量 cash max(cash, hold p) hold max(hold, -p) return cash顺序上先算cash因为cash依赖上一轮的hold如果先覆盖hold就会出错。这种细节做多了会发现DP的滚动变量版本比二维数组更容易写出隐蔽bug建议初学时先用数组版理清逻辑再优化成变量版。2.4 121题给后面留的钩子121题里真正重要的不是代码而是“持有”和“不持有”这个二元状态。122题完全复用二元状态只改买入时的状态来源123题则把二元状态扩展到五元状态。所以121是后面所有股票DP的基础把它彻底吃透后面两题就是加状态的问题。3. 122. 买卖股票的最佳时机II无限次交易下的贪心与DP3.1 贪心为什么成立无限次交易时只要存在价差就能赚。假设价格序列是[1, 3, 2, 4]最优做法是第1天买入第2天卖出赚2第3天买入第4天卖出赚2。总利润4。如果用贪心就是把所有“涨”的部分累加def maxProfit(prices): profit 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit这个解能过的原因在于一次完整的买卖可以拆成逐日差价。比如[1, 2, 3]第1天买第3天卖收益2等价于(2-1) (3-2)也是2。无限次交易下相邻上涨区间的累加就是所有正收益之和。3.2 同一套状态机只改一行如果沿用121的DP写法转移关系变为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])与121唯一不同是买入时用dp[i-1][1] - prices[i]也就是“以前一轮不持有时的现金余额作为买入资金基础”。为什么因为可以多次交易买入之前可能已经卖过不止一次现金余额不再是固定的0所以要取历史上最优的不持有状态。代码def maxProfit(prices): n len(prices) if n 2: return 0 dp [[0, 0] for _ in range(n)] dp[0][0] -prices[0] dp[0][1] 0 for i in range(1, n): 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][1]这种写法不比你单独背贪心方案差而且最重要的是它和121、123的DP框架完全统一。我建议至少把DP版本理解透因为面试时候考题的变体很多比如加上手续费、加上冷冻期贪心就未必有效而状态机DP往往只需要加状态。3.3 注意现金余额的变化有同学会问dp[i][0]和dp[i][1]到底代表什么是利润还是余额在初始化资金为0的设定下这两者可以统一理解为“账户现金余额”。买入时扣钱所以变成负数卖出时收钱所以变正。最终答案取dp[-1][1]因为不持仓时账户余额就是最大利润。理解了这个再看122题就不会出现“为什么买入时不是扣价格而是加负价格”这种疑惑了。4. 123. 买卖股票的最佳时机III两笔交易的状态机升级4.1 五个状态分别是什么最多两笔交易时整个操作过程被切成5个阶段状态0还没买过也没卖过。状态1已经买了第一次目前持有股票。状态2已经完成第一笔交易即卖出过一次目前不持有股票。状态3已经买入第二次目前持有股票。状态4已经完成第二笔交易即卖出过两次目前不持有股票。为什么需要5个状态因为你要同时知道两件事完成了多少笔交易、当前是否持仓。两笔交易就是“0笔、1笔、2笔”三个层级再叠加“持仓/不持仓”理论上可以拆成6种但“0笔且持仓”在无做空的前提下不可能出现所以实际是5种。4.2 状态转移的推演我直接写成dp[i][j]表示第i天结束后处于状态j的最大现金余额。转移公式dp[i][0] dp[i-1][0] 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]) dp[i][4] max(dp[i-1][4], dp[i-1][3] prices[i])状态0到状态0不需要操作状态1可以来自昨天的状态1继续持有也可以来自昨天的状态0第一次买入状态2可以来自昨天的状态2保持空仓也可以来自昨天的状态1第一次卖出状态3同理是第二次买入状态4是第二次卖出。这段公式写出来后你会发现它其实就是两套121/122的状态机首尾相接中间通过状态2和状态3衔接。4.3 初始化里的关键坑点初始化的写法是dp[0][0] 0 dp[0][1] -prices[0] dp[0][2] 0 dp[0][3] -prices[0] dp[0][4] 0最后两行是最容易让人疑惑的。第0天就处于状态3意思是“已经买了第二次并持有股票”你可能觉得这不合理因为第一天不可能完成两笔交易。从实际交易角度看确实不合理但在动态规划里这是合法的“状态初值”。理由是为了保证第二次买入可以由状态2在第一天之后顺利转移出来。如果我们把dp[0][3]设置成一个很小的负数如-inf那后续所有从状态3出发的路径都会被污染因为第一天无法进入状态3第二天也就无法从“昨天的状态3”转移出有效值。LeetCode官方题解里普遍采用“第0天允许重复买卖”的设定也就是说同一天买入再卖出再买入相当于没赚没亏但把状态机激活了。这样初始化dp[0][3] -prices[0]不会产生实际利润却能保持状态转移的完整性。4.4 完整代码与滚动数组写法二维DP版def maxProfit(prices): n len(prices) if n 2: return 0 dp [[0] * 5 for _ in range(n)] dp[0][0] 0 dp[0][1] -prices[0] dp[0][2] 0 dp[0][3] -prices[0] dp[0][4] 0 for i in range(1, n): dp[i][0] dp[i - 1][0] 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]) dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i]) return dp[-1][4]滚动变量版def maxProfit(prices): n len(prices) if n 2: return 0 s0 0 s1 -prices[0] s2 0 s3 -prices[0] s4 0 for p in prices[1:]: s1 max(s1, s0 - p) s2 max(s2, s1 p) s3 max(s3, s2 - p) s4 max(s4, s3 p) return s4这里特别提醒滚动变量版里s2的计算依赖旧的s1s3依赖旧的s2s4依赖旧的s3。如果按s1 - s2 - s3 - s4的顺序更新刚好每一条都用的是上一轮的值但前提是你没有在中间打印或复用已经被覆盖的变量。实际写的时候我建议在纸上把“旧状态变量”列出来然后再写更新顺序否则很容易出现串值问题。实际上上面这版代码能通过但如果你非要严谨可以用数组cur [0]*5并用临时变量复制旧值不过LeetCode上这个顺序是安全的因为公式里依赖的左值都在更新之前读取。5. 从121到123的纵向对比5.1 三题关键差异表题号交易次数贪心是否可行DP状态个数转移核心区别1211次可以记录最低价2买入时基于初始资金0所以是-prices[i]122无限次可以累加正差价2买入时基于前一日不持有现金dp[i-1][1] - prices[i]123最多2次不行5买入卖出各分两轮用状态区分第几笔这张表的核心记忆点是交易次数受限时需要把“已经完成的交易笔数”纳入状态交易次数无限时不需要记录笔数因为任何时候都可以再买再卖贪心或二维状态就够。5.2 通用思考框架我在刷完这三题后总结了一套比较通用的思考方式先明确题目限制条件中最关键的是哪一条是交易次数、持有股数、手续费、冷却期还是其他。把“当前是否持仓”作为基础状态。几乎所有的股票DP题都有这个维度。如果存在交易次数限制就再加一维表示“已经完成的交易次数”或“当前交易的状态阶段”。初始化时不要从实际生活合法性出发要从状态可达性出发。尤其是有限交易次数下的高阶状态常用一个“不产生利润但能激活状态”的初始值比如-prices[0]。写转移公式时只关注“今天从昨天的哪个状态来”不要脑补未来。这套框架不仅能解123还能直接迁移到188题最多k次交易、309题含冷却期、714题含手续费。我后来刷714时只改了买入或者卖出的公式其他骨架几乎原封不动。6. 实战踩坑与排查经验6.1 常见错误我做这三题时实测最容易踩的坑有四个。第一个坑是121里用dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i])。这么写代码多数情况下也能过因为初始资金是0且只允许一次交易后续dp[i-1][1]始终为0结果不会错。但理解上是有偏差的。第二个坑是123的初始化把dp[0][3]写成float(-inf)。这样写导致第一天无法进入第二次买入状态后面所有状态转移全都是负数无穷结果直接崩盘。需要记住这里是状态机不是真实交易激活状态比逻辑严谨更重要。第三个坑是滚动变量更新顺序。122改成变量版时如果你先更新hold再更新cash就会让新cash基于新hold结果完全错误。123同样有这个问题尤其当你以为“反正只用旧值”时最容易忽略。第四个坑是返回值选错。有人看到123最后返回max(dp[-1])觉得反正取最大就行。虽然本题最终答案通常是dp[-1][4]但写成max(dp[-1])在逻辑上不如dp[-1][4]清晰因为状态2也有可能是当前天数下最大余额但交易次数没到上限。真正面试时建议写清楚是“完成两次交易后的最大现金”。6.2 自查清单我每次写完一个股票DP题会按下面的清单自查一遍空数组和长度为1的数组是否处理。初始化时是否所有状态都有定义特别是有限次数的高阶状态。转移公式里的买入操作用的是“上一轮不持有状态”还是“初始资金0”。滚动变量版的更新顺序是否保证每个新状态都基于旧状态。返回值是否为最后一个状态而不是某个中间状态的max。用滚动数组后手动模拟[1, 2, 3, 4]和[7, 1, 5, 3, 6, 4]两个用例确认结果正确。这种模拟小用例的成本很低但能排查出绝大多数初始化问题。我建议别一上来跑LeetCode提交先自己在纸上跑一遍[1,2,3,4]答案是3再跑[7,1,5,3,6,4]121答案是7第2天买第5天卖122答案是7两段差价之和也是7123答案也是7。这三个用例非常重要因为121、122、123在同一个数组上结果可能相同导致你不容易发现状态写错。想区分就必须用类似[3,3,5,0,0,3,1,4]这种多峰数组三题答案分别是4、8、6这样才能完全验证状态机逻辑。6.3 再看一眼状态机的本质我个人刷完这三题后最大的体会是状态机DP不是背公式而是把“时间 状态”展开成一张表每天决策一次每个状态只从昨天的合法状态转移过来。股票系列之所以难更多是难在“状态的定义”和“初值的选择”而不是转移公式本身。比如123的状态如果你画一张图其实就是两条线第一次买入 - 第一次卖出 - 第二次买入 - 第二次卖出中间多了一个“已完成第一笔交易但还没开始第二笔”的空仓状态。只要能把这条线在数组里跑起来问题就解了一大半。写在最后的一点心得这三题刷完之后我建议你顺手把188题最多k次交易也看一眼。你会发现123只是188当k2的特例只需要把状态数改成2k1转移逻辑完全一致。股票系列练的就是这种“把业务限制翻译成状态维度”的能力翻译对了代码怎么写都顺翻译错了背再多模板也没用。如果只记一句话遇到股票买卖题先问自己“最多交易几次”“当前能不能持仓”“有没有冷却期或手续费”然后把约束全部映射到状态转移公式里问题就落地了。我自己在面试时遇到股票变体题也是这么拆的实测比硬背题解有用得多。