刷算法题刷到股票系列大概是最能体会“一道题吃透一类题”的阶段。我在代码随想录算法训练营的第49到51期里集中把121、122、123、188、309这五道买卖股票的最佳时机全部过了一遍。刚开始看到题号的时候觉得是五道独立题目真正坐下来推状态才发现它们就是同一个动态规划模板递进出来的五个版本一次买卖、无限次买卖、两次买卖、k次买卖、带冷冻期。这篇就把我在训练营里从第一题推到最后一题的完整思考过程写清楚包括状态定义是怎么一步步改出来的、代码长什么样、以及我自己踩过的几个坑。1. 股票系列里藏着的动态规划主线1.1 五道题到底在考什么这五道题表面上都是给一组价格数组让你在某个规则下获取最大利润但核心考点完全不同。121限定只能买卖一次很多人用贪心扫描最低点也能过122把限制放开成无限次交易贪心升级成“只要今天比昨天贵就累加”也能过但从123开始限制变成最多两次交易贪心就开始失效了因为你没法直观判断哪两次买卖能组合出最大利润。188把两次推广成最多k次309又额外塞了一个冷冻期这时候贪心的直觉基本就不管用了必须老老实实把状态机建出来。训练营里把这五道题安排在连续三期顺序是121、122、123、188、309这个顺序本身就是刻意设计的。121教会你二维dp的雏形122在同一个框架下改一个dp公式就通吃123让你意识到“交易次数”也得进状态188则是把123的状态数量参数化309再在状态转移上加一个约束。一道题改一步每一步改完回头看上一题都会觉得特别清晰。1.2 为什么贪心只在121和122有效很多人刷完121和122会误以为股票题就是贪心的套路我用亲身经历告诉你这个错觉很危险。121的贪心是维护历史最低价每天算一下“如果今天卖能赚多少”这是对的因为只买一次所以你只需要关注最低点122的贪心是收集所有上涨区间这也是对的因为无限次交易可以把每一段涨幅单独收割。但123的“最多两次交易”里两次交易是相互制约的第一笔买得太早、卖得太晚会影响第二笔买入的机会成本。这个约束没法用简单的“找两个最大的上涨区间”来刻画因为两段交易在时间上不能重叠你想让第二段收益大第一段就得及时收手。所以说贪心是股票系列的“新手村”真正的主线是动态规划。动态规划的优势在于它不需要你整体判断“该在哪天买哪天的”它只需要定义清楚每一天结束时可能处于什么状态然后把前一天的状态按规则推到后一天。这个思路一旦建立不管交易次数是2次还是k次不管是冷冻期还是手续费都是在“状态数量”和“转移条件”上做文章。2. 用121打开dp状态定义的大门2.1 持有与不持有状态机的最小单元121题的dp是我在训练营里反复读了好几遍才真正吃透的。很多题解一上来就甩公式但不解释为什么需要二维dp。我的理解是每天结束的时候你手里要么持有股票要么不持有这两种情况的现金余额是完全不同的所以你至少要用两个状态去记录。这里有一个容易想歪的细节dp存的是“现金余额”而不是“利润”。因为买卖动作会改变你的现金余额持有股票时余额是负的你花钱买了不持有且已经卖掉时余额是正的。所谓最大利润其实就是最终状态下能拿到的最大现金这种表述方式在动态规划里特别好用因为它天然处理了买入需要扣钱这件事。我用两个状态来定义dp[i][0]第i天结束时手里持有股票的最大现金余额dp[i][1]第i天结束时手里不持有股票的最大现金余额。2.2 121的完整推导与代码先看持有状态怎么转移。第i天结束手里有股票可以是第i-1天就已经持有然后今天继续拿也可以是今天刚买入。因为121限定只能买卖一次所以今天买入必然意味着之前没有过任何交易那买完之后手里现金就是 -prices[i]花了今天的价格买入没有别的选择。于是转移方程是dp[i][0] max(dp[i - 1][0], -prices[i]);再看不持有状态。第i天结束手里没股票要么是第i-1天就不持有继续空仓要么是第i-1天持有股票且今天把它卖掉了。如果今天卖出那“今天不持有”的现金就是“昨天持有”的现金加上今天的卖价dp[i][1] max(dp[i - 1][1], dp[i - 1][0] prices[i]);初始化第0天如果持有只能是以第0天的价格买入所以dp[0][0] -prices[0]不持有就是没买dp[0][1] 0。答案取dp[prices.size() - 1][1]因为最后一定是不持有才能拿到现金。C实现如下int maxProfit(vectorint prices) { if (prices.empty()) return 0; vectorvectorint dp(prices.size(), vectorint(2, 0)); dp[0][0] - prices[0]; dp[0][1] 0; for (int i 1; i prices.size(); 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[prices.size() - 1][1]; }这里有个小细节值得说为什么不是dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i])因为那是122题的公式。121里买之前不能有卖出操作所以买入时只能直接用-prices[i]不能拿前一天不持有的现金去减。这个区别就是一次买卖和多次买卖唯一的公式差别理解了这一点121到122就是一行代码的事。2.3 121的贪心直觉与dp的无缝衔接其实121也可以用滚动变量做空间优化只需要维护前一天的两个值因为每天早上只依赖昨天。代码可以压缩成两个int变量int hold -prices[0], cash 0; for (int i 1; i prices.size(); i) { int newHold max(hold, -prices[i]); int newCash max(cash, hold prices[i]); hold newHold; cash newCash; }但我不建议你在一开始就写这种压缩版因为它掩盖了状态转移的完整逻辑。训练营里反复强调一个理念先把二维dp写对再谈优化不要在脑子还没理清楚的时候就上来追求最短代码。后面123、188、309的推导都需要你拿着二维dp纸笔画滚动变量那个形式很容易让你漏状态。3. 123与188把“交易次数”做成状态3.1 为什么二维dp天然适合“k次交易”到了123题最多只能交易两次。这时候如果还用“持有/不持有”两个状态你就没法区分这到底是第一笔交易还是第二笔交易因为第二笔买入需要建立在第一笔已经卖出并且获得收益的基础上。解决办法就是给每一个状态前面加上“当前完成了第几次交易”这个维度。我用的是五个状态的写法题解里也叫状态机。状态0表示还没做任何操作状态1表示第一次买入后的持有状态状态2表示第一次卖出后的不持有状态状态3表示第二次买入后的持有状态状态4表示第二次卖出后的不持有状态。这里状态数量看起来多其实本质就是两个买卖周期每个买卖周期有两个子状态再加上一个初始的“无操作”状态。很多人第一次看到五个状态会觉得繁琐我当时的建议很简单你就把它当成两个121嵌套在一起。第一次买卖的求解逻辑和121一模一样第二次买卖的买入公式则需要参考第一次卖出后的现金余额。递推关系如下dp[i][0]继承dp[i-1][0]dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])第一次买入现金从0减去价格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])第二次卖出。3.2 123的初始化细节初始化是这道题最容易写错的地方。第0天手里没有任何操作的现金是0第一次买入现金变成-prices[0]第一次卖出当天买当天卖收益为0第二次买入相当于先买再卖再买还是-prices[0]第二次卖出也是0。int maxProfit(vectorint prices) { vectorvectorint dp(prices.size(), vectorint(5, 0)); dp[0][1] -prices[0]; dp[0][3] -prices[0]; for (int i 1; i prices.size(); i) { 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[prices.size() - 1][4]; }这里有一个我当初踩过的坑初始化dp[0][3]为-prices[0]让很多人不理解为什么第二次买入在第0天也发生了。其实你完全可以把它解释成“在同一天完成了第一次买入和第一次卖出然后立刻第二次买入”因为同一天先买后卖不影响最终收益所以把第二次持有状态也初始化为第0天买入是合理的且能保证后面递推不出现不合理的负无穷值。3.3 188的无限套娃k次交易的模板化写法188题把最多两次推广到最多k次如果沿用123的思路状态就得开成2k2个奇数下标表示持有偶数下标表示不持有0号状态永远是无操作。这个模板写出来特别工整也是训练营里我认为最值得背的一段代码。这里对j做遍历j从0开始每两个一组代表一个完整的买卖周期。状态递推可以统一成两条规则对于奇数状态持有由前一奇数状态继续持有或从上一偶数状态买入对于偶数状态不持有由前一偶数状态继续空仓或从上一奇数状态卖出。用C写就是int maxProfit(int k, vectorint prices) { if (prices.empty()) return 0; vectorvectorint dp(prices.size(), vectorint(2 * k 1, 0)); for (int j 1; j 2 * k; j 2) { dp[0][j] -prices[0]; } for (int i 1; i prices.size(); i) { for (int j 0; j 2 * k - 1; j 2) { dp[i][j 1] max(dp[i - 1][j 1], dp[i - 1][j] - prices[i]); dp[i][j 2] max(dp[i - 1][j 2], dp[i - 1][j 1] prices[i]); } } return dp[prices.size() - 1][2 * k]; }初始化循环里把所有奇数的持有状态都设成-prices[0]理由和123一样每一天都可以在逻辑上完成前面所有交易的买卖然后立刻进入第j/21次买入。这里的空间复杂度是O(n * k)如果题目把k给得很小跑起来完全没问题。我在训练营里见过不少人试图优化成O(k)的一维数组但我建议先按二维写。原因是二维的形式能让你随时打印dp表排查问题一维滚动数组省下来的那点空间在这个题量级上意义不大反而容易在更新顺序上翻车。尤其是内层循环如果从左往右更新一维数组里后面的状态可能用了本轮已经更新过的值导致计时序错误从右往左更新又要求你对状态依赖关系非常熟悉。先把二维写对优化永远是后话。4. 309冷冻期状态转移多一步4.1 冷冻期如何打破“卖完就能买”的假设309题的规则比188又加了一条你卖出股票后的第二天不能买入必须等一天。这个约束直接改变了一个前提——之前122里一个状态的转移可以依赖前一天不持有状态直接买入但现在不行因为那个不持有状态可能是“今天刚卖完”的明天买就会被冷冻期挡住。我的处理方式是把“不持有”拆成两个子状态一个是刚卖完股票、正处于冷冻期的状态另一个是已经过了冷冻期、可以自由买入的状态。持有状态本身不需要拆因为它已经持有股票了冷冻期只限制买入不限制卖出和持有。这样每天结束时有三种状态hold手里持有股票sold今天刚卖出处于冷冻期rest手里没有股票也不在冷冻期可以买。三个状态的转移逻辑是hold可以继续持有或者从rest买入sold只能由hold卖出转入等于hold加上今天的卖出价rest可以是昨天sold自然冷却的结果也可以是昨天就是rest今天继续休息。4.2 309的递推公式与初始化我把公式写出来对比着看就很清楚int maxProfit(vectorint prices) { if (prices.empty()) return 0; vectorvectorint dp(prices.size(), vectorint(3, 0)); dp[0][0] -prices[0]; // 第一天天买入 dp[0][1] 0; // 第一天不可能卖出 dp[0][2] 0; // 第一天也不在冷冻期 for (int i 1; i prices.size(); i) { dp[i][0] max(dp[i - 1][0], dp[i - 1][2] - prices[i]); dp[i][1] dp[i - 1][0] prices[i]; dp[i][2] max(dp[i - 1][1], dp[i - 1][2]); } return max(dp[prices.size() - 1][1], dp[prices.size() - 1][2]); }三个公式里最容易被忽视的是dp[i][1]没有max选项它就是dp[i-1][0] prices[i]因为“今天刚卖出”这个状态必然意味着昨天是持有的今天执行了卖出没有第二条路径。而dp[i][2]同时接受昨天sold和昨天rest的延续逻辑上就是“冷冻期会结束空仓可以继续空仓”。最后答案取max(sold, rest)因为没有必要再持有股票结束除非价格永远不涨——那结果就是0也就是rest状态从头到尾都是0的情况。4.3 309和前面的题怎么串起来做完309再回头看122你就会发现122是309的特殊版本没有冷冻期所以sold和rest可以合并成一个状态买入可以直接从不持有那边转移公式变成dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i])。这个递进关系对我来说是整期训练营最大的收获你不是在背五道题而是在用一道题的状态机模型覆盖另一个题的规则变化。如果你想把309也推广到“最多k次交易同时带冷冻期”那就把状态维度再叠加每个交易次数阶段都有持有、刚卖出、冷却完毕三个子状态。题目一般不这么出但道理是通的你理解了状态机的组合方式以后自己推这样的变体问题也只是时间问题。5. 训练营里的实战心得与避坑清单5.1 读题的边界条件最容易翻车训练营每天的打卡里最常见的错误集中在边界prices为空、prices只有一天、k大于实际可能交易次数。121和122的空数组直接返回0没问题但123和188的dp初始化如果没判空访问prices[0]就会越界。我当时在188里就吃过这个亏写完初始化循环之后直接跑一个空数组用例崩得毫无预兆。另一个容易忽略的点是prices长度为1时所有答案都应该是0因为你没法完成一次真正的买卖但这不代表你的dp表不会错。第0天初始化为-prices[0]第一天没有循环执行最后返回的结果如果是持有状态的负值那就说明你返回错了状态。永远记得最终状态必须是不持有。5.2 空间压缩是个陷阱不是加分项训练营里有些同学喜欢把dp数组压缩成几个变量看着代码短很爽但debug的时候特别痛苦。我记得自己写309时也尝试过只保留昨天的三个值写成单变量滚动结果漏了一个“同一轮内状态不能互相覆盖”的关键细节如果你用新算出来的sold直接参与这一轮的rest计算整个状态机就乱套了。正确的滚动写法需要先暂存昨天的所有状态再用旧值算新值。我的经验是刷题阶段尤其是训练营打卡阶段先保证二维dp完全跑通再谈压缩。甚至可以说股票系列这五道题用二维dp的代码量也完全在面试手写可接受的范围内面试官更看重你能不能讲清楚每个状态的含义而不是你能不能写出一行流代码。5.3 打印dp表来验证你的理解这是我强烈推荐的学习方法。每写完一道题不要急着提交把dp表打印出来看几行数据。拿121举例你打印出每一天的持有和不持有现金能看到持有状态的出现时机就是最低价买入的时机卖出状态的最大值就是最终收益。拿123举例打印五个状态你能清楚地看到第二次买入状态在某一天从一个很大的负数变成相对小的负数说明第一次卖出的大幅盈利被带入到了第二次买入中。打印dp表最大的好处是把抽象的状态转移变成可视化的过程。我也用过一些可视化工具但最方便的还是在代码里临时加一个cout循环。训练营的代码随想录里其实也多次提到这种排查思路配合题目看特别管用。5.4 这套题的面试价值与应答策略如果面试官考这道股票系列通常不会只考121这种热身题大概率是升级到123或309。我的建议是先把状态机的思考方式讲出来——每天结束有哪些状态、状态之间怎么转移、为什么需要这些维度而不是一上来就默写标准答案。面试官听到你能从121推到188基本就认可你对动态规划的理解深度了。我自己在训练营打完这套题之后的体会是股票系列的真正价值不是让你记住五段代码而是让你亲身体会一次“状态设计”的完整过程。一开始你看到题目只能想到贪心做完123你已经能感受到状态拆分的力量等到309收尾时你会习惯性地问自己这个题目比上一题多了一个什么约束这个约束应该变成一个新的状态维度还是改变某个转移公式养成这个思考习惯以后动态规划的题基本就入门了。