企业官网建设流程全解析

刷算法题刷到股票系列，大概是最能体会“一道题吃透一类题”的阶段。我在代码随想录算法训练营的第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(vector<int>& prices) { if (prices.empty()) return 0; vector<vector<int>> dp(prices.size(), vector<int>(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(vector<int>& prices) { vector<vector<int>> dp(prices.size(), vector<int>(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的思路，状态就得开成2k+2个，奇数下标表示持有，偶数下标表示不持有，0号状态永远是无操作。这个模板写出来特别工整，也是训练营里我认为最值得背的一段代码。

这里对j做遍历，j从0开始，每两个一组代表一个完整的买卖周期。状态递推可以统一成两条规则：

• 对于奇数状态（持有）：由前一奇数状态继续持有，或从上一偶数状态买入；
• 对于偶数状态（不持有）：由前一偶数状态继续空仓，或从上一奇数状态卖出。

用C++写就是：

int maxProfit(int k, vector<int>& prices) { if (prices.empty()) return 0; vector<vector<int>> dp(prices.size(), vector<int>(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/2+1次买入。这里的空间复杂度是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(vector<int>& prices) { if (prices.empty()) return 0; vector<vector<int>> dp(prices.size(), vector<int>(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收尾时，你会习惯性地问自己：这个题目比上一题多了一个什么约束？这个约束应该变成一个新的状态维度，还是改变某个转移公式？养成这个思考习惯以后，动态规划的题基本就入门了。