打卡第41天今天把买卖股票系列的前三题一次收拾干净121、122、123。很多人刷到这三题会有一个共同的困惑为什么121用贪心能写122用贪心也能写到了123突然就不能贪心了为什么明明都是“买卖股票”解法一会儿一个样其实这三题背后共用同一套动态规划状态机框架只是每题的交易次数限制不同导致状态数量和转移方式发生微妙变化。这篇文章不打算只给题解而是把暴力思路、贪心思路、DP状态机思路串成一条线从121起步一路推到123顺便把滚动数组、初始化边界这些高频踩坑点都摊开讲清楚。适合正在刷动态规划、或者面试前突击股票题型的读者保证看完能自己手写出来而不是只会背代码。1. 先搞懂这一组题到底在问什么1.1 三题的差别只有“交易次数”把三道题放在一起看题目背景一模一样给定一个数组 pricesprices[i] 表示第 i 天的股票价格求能获得的最大利润。唯一区别是交易次数限制题号交易次数限制典型解法121只能买卖一次贪心 / 二维DP122可以买卖无限次贪心 / 二维DP123最多买卖两次四状态DP / 通用k次DP这个限制直接决定了题目的难度层级。121是最简单的一档一次交易嘛本质上就是“找一对最低买点、最高卖点”122放开次数以后反而可以用贪心做因为次数不再构成约束每个上涨区间都能吃满123卡在中间限制两次交易既有“限次”的约束又不像 k 次那么抽象是学习状态机最合适的切入点。1.2 为什么这类题最后都会落到DP一开始学股票题很多人的第一反应是穷举所有买入日、所有卖出日两重循环直接算。这个思路对121是可行的O(n²)对122就爆了因为你得枚举任意多次交易的组合复杂度直接指数级。再从贪心角度想贪心能处理的情况其实非常有限。121能贪心是因为“一次交易”时最优卖点对应的最优买点就是它之前的历史最低价这是一个前缀最值问题122能贪心是因为交易次数无限任何上升段都可以单独收割局部最优就是全局最优。一旦出现“最多两次”这种限制局部最优就不再等于全局最优——你可能需要为了第二次交易主动放弃第一次交易的某段利润。这时候就需要DP登场DP不追求每一步局部最优而是把“当前赚了多少钱 手里有没有股票”作为状态用转移方程枚举所有可能路径保证全局最优。1.3 先建立状态机直觉持有与不持有后面123要用的状态机思维其实在121就能建立起来。任意一天结束后你的账户只可能处于两种状态持有股票或者不持有股票。所有买卖决策本质上就是在这两种状态之间切换。121是“最多切换一次买入→卖出”122是“可以任意多次切换”123是“最多切换两次”。这样看三道题就是同一棵树的三个分支区别只是状态细分的层次不同。2. 121一次交易先把最简单的模型吃透2.1 题目还原与暴力思路121问的是只能选择某一天买入并在之后的某一天卖出求最大利润。最朴素的写法就是二重循环枚举买入日 i 和卖出日 jj i维护价格差的最大值。这个解法能过小数据但O(n²)显然不够看而且它没有揭示问题的结构对后续题目也没有迁移价值所以只作为切入思路。2.2 贪心解法记录历史最低点一次交易的最优解一定是“在前面某天买在后面某天卖”。如果固定卖出日那买入日必须选在它之前价格最低的那一天。于是可以只遍历一遍维护一个“已经出现过的最低价 minPrice”每到一个新价格就尝试用它去减 minPrice不断更新答案class Solution { public: int maxProfit(vectorint prices) { int minPrice INT_MAX; int ans 0; for (int p : prices) { minPrice min(minPrice, p); ans max(ans, p - minPrice); } return ans; } };这就是前缀最值的思想遍历到第 i 天时minPrice 是 prices[0..i] 的最小值p - minPrice 是以第 i 天卖出能拿到的最大利润。因为只需要一次交易不存在“之前的利润”需要累加所以这个简单解法就是题目本身的最优解时间O(n)空间O(1)。2.3 DP解法两个状态从零开始如果只为了通过121贪心已经够了。但为了后面122和123最好从这题就开始用DP的视角看问题。定义两个状态dp[i][0]第 i 天结束后手里持有股票账户最高现金余额dp[i][1]第 i 天结束后手里不持有股票账户最高现金余额注意这里“现金余额”可以是负数比如花了钱买入现金就是负的。初始状态下第0天如果买入现金变成 -prices[0]所以 dp[0][0] -prices[0]不持有则为0。转移方程dp[i][0] max(dp[i-1][0], -prices[i]) dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i])第二个式子很好理解第 i 天不持有要么昨天也不持有要么昨天持有、今天卖出现金加上今天的价格。第一个式子是重点第 i 天持有要么昨天就持有要么今天买入。但“今天买入”为什么是 -prices[i]而不是 dp[i-1][1] - prices[i]因为121只允许一次交易买入之前账户里一定没有任何交易利润初始现金是0所以买入后现金就是 -prices[i]。这个细节特别关键到了122改的正是这一行。class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); vectorvectorint dp(n, vectorint(2)); dp[0][0] -prices[0]; dp[0][1] 0; for (int i 1; i n; i) { 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[n-1][1]; } };最后答案取 dp[n-1][1]因为最终手里不持有股票才代表钱真正到手如果取 dp[n-1][0]说明最后一天还持仓利润没兑现。2.4 滚动数组优化从二维压到两个变量观察转移方程dp[i] 只依赖 dp[i-1]所以完全不需要整个二维数组。用两个变量 hold 和 empty 分别表示“持有”和“不持有”遍历时同步更新int hold -prices[0]; int empty 0; for (int i 1; i n; i) { int newHold max(hold, -prices[i]); int newEmpty max(empty, hold prices[i]); hold newHold; empty newEmpty; }这里我故意用 newHold、newEmpty 两个临时变量而不是直接原地更新。原因在于 newEmpty 要用到旧的 hold如果先更新 hold 再更新 emptyempty 就会用到今天买入后的持有状态逻辑上已经不对了。121里因为公式特殊原地更新可能结果恰好一样但到123的4状态DP里这个坑会直接导致答案错误所以从121开始就养成“先算新值再统一赋值”的习惯后面能省很多事。3. 122放开次数限制贪心起飞DP也升级3.1 无限次交易意味着什么122允许你在任何时候买入、卖出但同一时间只能持有一股。所谓“无限次”其实可以理解成“每天都能重新决策”。一个绕不开的前提是同一天可以卖出再买入吗理论上题目没有禁止而且从DP角度这不会产生额外收益价格相同买卖相抵等于没操作所以许多题解都会默认允许这种操作。正因如此122才能用贪心。3.2 贪心做法累计所有正差价只要今天的价格比昨天高就认为赚到了这个差价。把所有正差价累加起来就是最大利润class Solution { public: int maxProfit(vectorint prices) { int ans 0; for (int i 1; i prices.size(); i) { if (prices[i] prices[i-1]) { ans prices[i] - prices[i-1]; } } return ans; } };为什么正确一段连续上涨的价格比如 [1, 2, 4]如果从1买入、4卖出利润是3但拆成1买2卖赚1、2买4卖赚2总利润还是3。所以无限次交易时只要价格在涨每天“高抛低吸”就能把整段涨幅全部吃掉。反过来下跌段不参与交易忽略即可。最后的总利润等于所有相邻价格上涨幅度之和这其实就是把所有波峰与波谷之间的差额累加起来。3.3 DP做法唯一的区别在买入那一行如果把121的DP拿过来只需要改一个地方买入时能不能使用之前赚到的利润。121里买入前现金是0因为只能买一次没有“之前的交易”122里可以无限次交易买入之前完全可能带着上一笔买卖赚的钱所以转移变成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][0] 的“今天买入”从 -prices[i] 换成了 dp[i-1][1] - prices[i]。这就是“允许使用历史利润买入”的含义。class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); vectorvectorint dp(n, vectorint(2)); dp[0][0] -prices[0]; dp[0][1] 0; for (int i 1; i n; i) { 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[n-1][1]; } };滚动数组版本也同步升级int hold -prices[0]; int empty 0; for (int i 1; i n; i) { int newHold max(hold, empty - prices[i]); int newEmpty max(empty, hold prices[i]); hold newHold; empty newEmpty; }3.4 贪心还是DP怎么选面试时做122建议先讲贪心O(n)时间、O(1)空间、代码短而且逻辑直观。但最好补一句“这题也可以用两状态DP做DP的好处是能扩展限制次数的场景”然后引出123。千万不要只会贪心面试官一旦追问“那如果最多只能买卖两次怎么做”直接卡壳就得不偿失了。实际上122用DP也完全不亏因为这套状态机框架就是把121到123打通的钥匙。4. 123最多两次交易状态机正式登场4.1 贪心失灵的反例先说结论123不能直接用122的贪心。原因很简单无限次交易时每一段上涨都可以单独收割但最多两次交易时如果出现了三段上涨你必须决定放弃哪一段或者把某两段合并成一次交易。贪心的“每段都取”在这里就不再是全局最优。举个例子prices [1, 2, 4, 2, 5, 7, 2, 4, 9, 0]。无限次贪心会把三段上涨全吃掉1买4卖赚32买7卖赚52买9卖赚7总计15。但限制两次交易后最优方案可能是1买7卖赚6再2买9卖赚7总计13或者2买7卖赚5加2买9卖赚7总计12反正到不了15。因为必须做出取舍只能靠DP枚举所有“两次交易”的组合。4.2 四个状态分别是什么既然最多两次交易过程可以拆成四个阶段状态0第一次买入后手里持有股票状态1第一次卖出后手里没有股票已经完成一次完整交易状态2第二次买入后手里持有股票状态3第二次卖出后手里没有股票已经完成两次完整交易每个状态存的是“处于该阶段时账户里的最高现金余额”。注意状态之间是有顺序的不能跳级不可能没经过第一次买入就直接第二次买入也不可能没经过第一次卖出就直接第二次卖出。4.3 状态转移方程推导先看状态0第一次持有要么昨天就已经第一次持有了延续下来要么今天第一次买入买入前的现金是0。dp[i][0] max(dp[i-1][0], -prices[i])再看状态1第一次卖出后空仓要么昨天就已经完成第一次卖出要么昨天还是第一次持有今天卖出现金增加 prices[i]。dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i])状态2第二次持有是很多人绕不清的地方要么昨天就已经第二次持有要么今天第二次买入。但如果今天买入前提是“已经完成第一次卖出”所以要用第一次卖出后的现金 dp[i-1][1] 减去今天的价格dp[i][2] max(dp[i-1][2], dp[i-1][1] - prices[i])状态3第二次卖出后空仓要么昨天就已经完成第二次卖出要么昨天是第二次持有今天卖出dp[i][3] max(dp[i-1][3], dp[i-1][2] prices[i])这四条转移里最关键的是状态2必须依赖 dp[i-1][1] 而不是 dp[i][1]。因为“第二次买入”这个动作必须发生在“第一次卖出”这个状态之后如果用了今天已经更新过的 dp[i][1]就等价于允许“昨天第一次卖出、今天第二次买入”听起来好像也合理但DP迭代的语义要求每个状态都从昨天递推过来跨天的动作必须用昨天的值否则会破坏状态的层次性。这个细节等一下在滚动数组部分还会再踩一次。完整代码class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); if (n 0) return 0; vectorvectorint dp(n, vectorint(4)); dp[0][0] -prices[0]; dp[0][1] 0; dp[0][2] -prices[0]; dp[0][3] 0; for (int i 1; i n; i) { 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[n-1][1], dp[n-1][3]); } };4.4 初始化为什么可以这样设第0天的四个状态dp[0][0] -prices[0]dp[0][1] 0dp[0][2] -prices[0]dp[0][3] 0。很多人疑惑第0天怎么可能同时处于“第二次买入”状态这里是在用DP边界技巧允许第0天完成一次“买入→卖出→再买入”的循环操作。因为第0天买入卖出价格都是 prices[0]相互抵消后现金变化是-p p - p -p效果上等于第0天直接持有股票但状态已经推进到“第二次持有”。这样做的目的是让后续状态转移不丢机会——如果 dp[0][2] 设为负无穷那第一次卖出后转到第二次买入时边界条件会非常别扭甚至可能漏算最优解。4.5 滚动数组的更新顺序坑把四个状态压成四个变量最容易踩的坑就是原地更新时的顺序。有人会写成int a -prices[0], b 0, c -prices[0], d 0; for (int i 1; i n; i) { a max(a, -prices[i]); b max(b, a prices[i]); // 这里的a已经是今天的了 c max(c, b - prices[i]); // 这里的b已经是今天的了错误 d max(d, c prices[i]); }问题出在 c 的更新c 依赖的是“前一天”的 b也就是第一次卖出状态。如果 b 已经先用今天的数据更新过了c 就等于允许“今天第一次卖出后又在今天第二次买入”把两个动作压缩在同一天完成结果会偏高。稳妥办法有两种一是像前面121那样先把四个新值算好再统一赋值二是倒序更新从 d 到 aint a -prices[0], b 0, c -prices[0], d 0; for (int i 1; i n; i) { d max(d, c prices[i]); c max(c, b - prices[i]); b max(b, a prices[i]); a max(a, -prices[i]); }倒序更新的逻辑是后面的状态如 d依赖前面的状态如 c先更新后面的保证它用的是前一天的 c再更新 c 时b 还是前一天的值不会串。两个方案都可以我个人的建议是“新值统一赋值”因为看着更直白不用想顺序问题。4.6 手推一遍示例数据用 LeetCode 官方示例 prices [3, 3, 5, 0, 0, 3, 1, 4] 手推一遍检验转移是否正确。为了简洁这里直接用四个变量第0天a-3b0c-3d0。第1天价格为3a-3b0c-3d0。第2天价格为5a-3b2-35c-3d2-35。第3天价格为0a0今天买入花费0现金0b2c2b-02d2。第4天价格为0a0b2c2d2。第5天价格为3a0b303c2d523。第6天价格为1a0b3c2b-12d5。第7天价格为4a0b404c2d624。最终答案是6。最优路径也很清楚第3天买入价格0第5天卖出价格3赚3第6天买入价格1第7天卖出价格4赚3合计6。手推一遍之后整个状态机的流动方向会非常直观。5. 三题的递进规律从两状态到四状态再到k次通用模型5.1 对比一下三道题的转移差异把三道题的状态转移放在一起看规律马上显形题目状态数买入时用的钱核心区别1212固定初始现金0只能买一次买入不能使用以前利润1222dp[i-1][1] - price可多次买买入可以使用之前累计利润1234第一次买入用0第二次买入用第一次卖出后现金需要记录交易次数状态拆分121到122的区别只在买入那一行122到123的区别则是把一个“空仓状态”拆成了“第一次卖出后空仓”和“第二次卖出后空仓”把一个“持有状态”拆成“第一次持有”和“第二次持有”。整个变化过程是有逻辑的不是靠死记硬背。5.2 通用 k 次交易模板把123继续推广到任意 k 次交易就是LeetCode 188。定义 dp[i][j][0] 表示第 i 天结束后已经完成了 j 笔交易手里没有股票dp[i][j][1] 表示第 i 天结束后已经完成了 j 笔交易手里有股票。转移方程dp[i][j][0] max(dp[i-1][j][0], dp[i-1][j-1][1] prices[i]) dp[i][j][1] max(dp[i-1][j][1], dp[i-1][j][0] - prices[i])第一行表示今天空仓要么昨天也空仓要么昨天持股、今天卖出并且这个卖出操作使得“已完成交易数”从 j-1 跳到 j。第二行表示今天持股要么昨天也持股要么昨天空仓、今天买入买入不增加已完成交易数。对123来说令 k2再处理一下 j0 的边界就能直接套用这个三维模板。实际做题时124以上用模板更省事而123直接用四状态更清晰因为只有两次交易四状态不会被维度压垮。5.3 顺手把股票系列变体也看穿LeetCode 股票题不止这三道后面还有309含冷冻期、714含手续费。它们的本质依然是状态机只是状态数量再增加309需要在“空仓”状态外再增加一个“冷冻期”状态714则只需要在每次卖出的收益里减去手续费。如果把121到123的状态机搞明白了变体题就是“在已有状态图里加节点、改转移”难度会断崖式下降。这也是为什么刷这类题一定要先弄懂状态定义而不是背代码。6. 常见问题与踩坑实录6.1 初始化到底该怎么设123最常翻车的点就是初始化。如果不把 dp[0][1] 和 dp[0][3] 初始化为0而是设成负无穷转移方程里 max 可能一直保留负无穷导致最终答案变成负数。反过来如果把 dp[0][2] 设成负无穷也容易漏状态。建议直接记住这套边界第一天“买入→再买入”等效为持有股票所以 dp[0][0] 和 dp[0][2] 都是 -prices[0]dp[0][1] 和 dp[0][3] 都是0。这套写法的合理性在于DP允许“同一天完成无成本操作”它不影响答案但统一了状态语义。6.2 滚动数组的原地更新顺序121和122用两个变量时如果不注意顺序因为公式特殊结果可能碰巧没问题。到了123四个变量原地更新一旦按顺序从a到d更新c就会吃到当天更新过的b导致第二次买入被错误提前。这里再强调一次要么全部用新变量暂存newA、newB...要么倒序更新。不要赌自己的运气直接采用规范写法。6.3 答案到底取哪个状态121和122的答案取 dp[n-1][1]也就是最后一天不持有股票。123要取 dp[n-1][1] 和 dp[n-1][3] 里的较大值因为最多两次交易有可能最优解只做了一次买卖。很多人会问取 dp[n-1][3] 行不行大部分用例能过但从语义上讲不严谨因为某些极端情况下只做一次交易更优dp[n-1][1] 会大于 dp[n-1][3]。稳妥写法就是两者取max。6.4 不要和最大子数组和搞混LeetCode 53题最大子数组和也是单次最优用的是Kadane算法很容易和121混淆。但121求的是两个价格差的最大值不是连续区间的累加和两者统计口径完全不同。千万别把Kadane的转移方程直接抄到股票题上或者反过来拿股票题的思路去套最大子数组和都会得出错误结论。6.5 刷题建议手推两遍比抄十遍管用股票系列学到这里强烈建议自己完整手推两遍第一遍开二维dp数组把每一天的四个状态都填出来第二遍用滚动数组重新推一遍。手推的意义不是模拟代码运行而是逼自己理解每个状态从哪来、到哪去。我见过很多人代码看了几十遍一到手写就卡住就是因为没真正自己走通一遍状态表。做完这个练习后面再遇到309、714甚至其他状态机DP都会觉得顺畅很多。我个人做这组题最深的体会是状态定义永远是第一步也是最需要花时间的一步。121到123看起来是“一道题加了个次数限制”其实是让你练习同一个核心模型在不同约束下如何演进。把这个过程走顺你收获的不只是三道题的AC代码而是应对整个状态机DP类题目的通用能力。Day41的股票三连击值得反复刷到闭眼能写为止。