训练营第四十天的题单放在一起群里直接炸了188、309、714三题全是“买卖股票的最佳时机”系列的进阶版。刷到这你会发现前面还在讲贪心、讲普通状态转移现在突然要同时处理交易次数、冷冻期、手续费三个额外条件。先别慌这三道题看着吓人但本质上共用同一套动态规划模型——如果你搞懂了“股票状态机”这个思路它们就是同一个模板换了三次参数。这篇就按我实际刷题时的顺序来聊先解188把“最多k次交易”这个最通用的模型打通再上309看冷冻期是怎么在状态图里多卡一个“冷静”节点最后是714手续费说白了就是在卖出时多扣一笔钱。顺带会把初始化、边界条件、滚动数组这些容易被细节绊倒的地方全部摊开讲。适合的人群很明确DP已经入门、想系统吃透股票专题或者面试前准备动态规划的读者这篇可以直接当复习笔记用。1. 三道题放一起刷才能看懂股票DP的套路1.1 从“一次买卖”到“带约束买卖”递进关系在哪先盘一下这个系列在LeetCode上的完整梯度121只能买卖一次122可以无限次买卖123限制最多两笔188把123推广成最多k笔309在无限次基础上加了冷冻期714在无限次基础上加了手续费。这里有个很关键的认知121、122、123、188是在“交易次数”这个维度上递进而309、714是在“交易规则”上做约束。前者考验你对状态维度的抽象能力——从1次扩展到2次就能劝退一批人扩展到k次更是让很多人直接写错数组大小后者考验你对“额外状态”的敏感度——冷冻期本质上是给空仓状态再拆成“能买”和“不能买”两种手续费则只是在利润计算时多一个减法。把这些题放在同一天刷的价值就在这里你能清楚地看到所谓的“新题”并不是全新的解题思路而是在同一个状态机上加点约束。先学会画状态转移图后面所有变体都是在图里增加节点或修改边权。1.2 股票DP的核心建模方式用状态图代替背公式做股票类DP我的习惯是永远先问自己一句话每天交易结束后我可能处于哪几种状态而不是一上来就背转移公式。为什么强调“结束后”因为股票交易是按天发生的你需要在第i天做决策买、卖、还是什么都不干。如果定义成“第i天操作完成后”的状态那第i天买入的收益就只依赖第i-1天的状态天然规避了“今天买入今天卖出”这种没有意义的闭环。这个时间点的选择决定了后面所有转移方程是否干净。用生活话来说你每天早上手里有一笔现金和一笔股票仓位一天结束时你的资产组合变成什么样子取决于你今天的操作。dp数组记录的就是在不同状态下能拿到的最大利润。状态有多少种取决于题目给了多少约束有没有交易次数限制有没有冷却期有没有手续费。股票DP的所有公式都只是这个状态图在不同约束下的投影。1.3 为什么这类题刷一道没用要三题连刷单刷188你可能学会了一个“奇数持有、偶数空仓”的数组技巧但脑子里的模型还是散的只刷309你记住了“卖出后要冷冻一天”但没意识到这只是状态图里多了一个节点。三题连在一起你会发现状态转移这个事是有肌肉记忆的画状态、写转移、定初始、算答案永远是这四步。更重要的是面试的时候面试官很喜欢在这个系列上做组合变化。今天考冷冻期明天可能问“手续费改成分段计费”后天可能问“最多k笔且带冷冻期”。如果你只是背过某一道题的代码遇到组合题就废了但如果你脑子里装的是“状态机”这个框架任何新约束都只是在图上加一笔的事。这也是为什么我强烈建议把这三题当成一个整体来学而不是零散地刷。2. 188题k次交易核心是把状态数组“复制两份”2.1 状态定义把k笔交易拆成2k个状态188题“买卖股票的最佳时机IV”题目要求最多完成k笔交易。123题是k2的特例当时用4个状态还能勉强手写扩展到k就必须建立通用的状态编号。我的定义方式是这样用一维状态下标j表示当前处于“第几笔交易的什么阶段”其中j 0空仓还没做过任何交易j 1持有第一笔股票j 2完成第一笔交易空仓j 3持有第二笔股票j 4完成第二笔交易空仓...规律很明显奇数下标代表“持有中”偶数下标代表“空仓中”。总共有2k1个状态下标从0到2k。为什么要多一个0因为它表示“从未买入”的初始状态这个状态在转移中非常重要确保第1笔买入的金额不会被错误累积。持有状态和空仓状态交替出现每次买入让下标加1每次卖出也让下标加1。这样写代码的时候只需要判断j的奇偶性就能确定该用哪条转移规则非常规整。2.2 转移方程与完整代码奇数持有、偶数空仓有了状态编号转移方程就顺理成章了。对于第i天、状态j如果j是偶数空仓今天可以继续空仓也可以从“持有状态”卖出。所以 dp[i][j] max(dp[i-1][j], dp[i-1][j-1] prices[i])如果j是奇数持有今天可以继续持有也可以从“空仓状态”买入。所以 dp[i][j] max(dp[i-1][j], dp[i-1][j-1] - prices[i])唯一需要注意的是j-1不能越界。j0时没有上一个状态它只能继续空仓所以偶数状态的j0才执行买卖逻辑。完整代码如下class Solution { public: int maxProfit(int k, vectorint prices) { int n prices.size(); if (n 0 || k 0) return 0; // 一笔完整交易至少需要两天实际有效交易次数不会超过 n / 2 k min(k, n / 2); // 0 ~ 2*k 一共 2*k1 个状态 vectorvectorint dp(n, vectorint(2 * k 1, 0)); // 第0天所有奇数状态持有初始化为 -prices[0] for (int j 1; j 2 * k; j 2) { dp[0][j] -prices[0]; } for (int i 1; i n; i) { for (int j 0; j 2 * k; j) { if (j % 2 0) { // 空仓状态 dp[i][j] dp[i - 1][j]; if (j 0) { dp[i][j] max(dp[i][j], dp[i - 1][j - 1] prices[i]); } } else { // 持有状态 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]); } } } // 最终答案完成最后一笔交易后的空仓状态 return dp[n - 1][2 * k]; } };这个写法我在本地跑过官方测试用例和题解预期完全一致。核心就是理解偶数状态用“卖出”转入奇数状态用“买入”转入两个方向对应两种操作。2.3 k大于n/2时为什么可以先降级处理很多人一开始不注意k的取值范围直接把数组开成2*k1。如果k很大比如10万而prices只有3天这就会创建20万列纯属浪费。一个简单的数学结论一笔完整的交易至少需要两天一天买入一天卖出所以n天最多完成n/2笔交易。只要k大于等于n/2实际约束就失效了等价于122题的无限次交易。处理方式就是在dp之前先做一次降级k min(k, n / 2);这样数组大小始终可控。但要注意k0时要单独返回0否则循环里会创建只有1列的数组逻辑上虽然没错但没必要。2.4 初始化容易翻车第0天所有持有状态怎么填第0天的初始化是188题最容易写错的地方。很多人的第一反应是dp[0][1] -prices[0]其他持有状态都应该是极小值。但在代码随想录的标准写法里所有奇数状态都直接初始化为-prices[0]。为什么这样也能对因为在第0天买入第一笔的最优利润就是-prices[0]。对于“持有第二笔”如果从第1天开始转移它会被dp[0][2]买入得到而dp[0][2]此时继承的是0所以dp[1][3] max(dp[0][3], dp[0][2] - prices[1]) max(-prices[0], -prices[1])。也就是说“持有第二笔”的初始资金来自“完成第一笔”后的空仓利润0再买入第二笔——0 - prices[1]是合法的。此时dp[0][3]-prices[0]虽然从字面上看是“第0天买了第二笔”但在max运算里它不会优于未来真实的买入操作所以不影响最终结果。如果还是觉得别扭你可以把所有奇数状态初始化成 INT_MIN / 2然后在转移时跳过非法值。但对面试来说写-prices[0]更简洁而且只要理解了上面这个“不变坏”的道理就不会被面试官问倒。3. 309题冷冻期只卡“买入”一条路3.1 冷冻期到底为什么难309题“最佳买卖股票时机含冷冻期”规则是卖出股票后的第二天不能买入。也就是说今天卖出明天处于冷却状态不能买后天才能重新买入。难点在于两状态DP持有/不持有在冷冻期规则下不够用了。因为“不持有”有两种完全不同的情况——一种是可以自由买入一种是昨天刚卖完、今天被迫冷静。这两种状态对未来决策的影响不同可买入状态能直接买冷静状态必须再多等一天。所以必须把“不持有”拆成两个状态。这也是状态机思维的价值遇到新约束先问自己“原有的状态分类是否足够表达当前规则”。不够就拆。3.2 三状态转移公式与代码我用三个状态来表示第i天结束后的情况状态0持有股票状态1不持有股票且处于冷冻期也就是今天刚卖出状态2不持有股票且不在冷冻期可以自由买入转移逻辑如下状态0持有今天继续持有或者今天从“可自由买入”状态买入。注意买入只能从状态2来不能从状态1来因为状态1是冷冻期不能买。 dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i])状态1冷冻期今天不持有且冷冻只可能是昨天持有今天卖出。 dp[i][1] dp[i-1][0] prices[i]状态2可买入空仓今天不持有也不冷冻可能是昨天就处于冷冻期、今天解冻了也可能昨天本来就是可买入空仓。 dp[i][2] max(dp[i-1][1], dp[i-1][2])代码class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); if (n 0) return 0; // 0: 持有 1: 空仓且冷冻 2: 空仓且可买 vectorvectorint dp(n, vectorint(3, 0)); dp[0][0] -prices[0]; dp[0][1] 0; dp[0][2] 0; for (int i 1; i n; 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]); } // 最后一天持有不如卖出所以答案在状态1和状态2里 return max(dp[n - 1][1], dp[n - 1][2]); } };用官方示例prices [1,2,3,0,2]跑一遍结果是3最优路径是第0天买入、第1天卖出赚1然后等第3天买入、第4天卖出赚2。中间第2天处于冷冻期不能买这个例子把规则展示得非常直观。3.3 状态压缩要注意求值顺序二维数组写对了之后很多人想优化成几个变量。这时候就会踩一个经典坑直接原地更新后面的状态用了被覆盖过的旧值。比如有人写成// 错误示范 for (int i 1; i n; i) { dp0 max(dp0, dp2 - prices[i]); dp1 dp0_old prices[i]; // 这里的 dp0 已经被更新了 dp2 max(dp1_old, dp2); }问题在于计算dp1时需要的是前一天持有状态的旧值但dp0已经被今天的值覆盖了计算dp2时需要的是昨天冷冻状态的旧值但dp1可能刚被覆盖。结果整个链条串味。正确做法是先缓存旧值int hold -prices[0]; // 持有 int cool 0; // 空仓且冷冻 int rest 0; // 空仓且可买 for (int i 1; i n; i) { int preHold hold, preCool cool, preRest rest; hold max(preHold, preRest - prices[i]); cool preHold prices[i]; rest max(preCool, preRest); } return max(cool, rest);这里每一步用的都是“前一天”的值顺序就不再影响正确性。这个坑在面试手写代码时特别容易暴露我建议刷题阶段就把缓存旧值的习惯养好。3.4 冷冻期加上交易次数限制怎么扩展思路如果面试官在309基础上追问一句“最多k笔且带冷冻期”不要慌。思路是让状态多一个交易次数的维度dp[i][k][0]表示经历过k笔交易后持有dp[i][k][1]表示经历过k笔交易后空仓且冷冻dp[i][k][2]表示空仓且可买。转移规则几乎不变只是买入和卖出时把k的计数变化写清楚。状态图还是那张状态图只是从二维变成了三维。这就是状态机模型的可扩展性。4. 714题手续费本质是给“卖出”加负担4.1 手续费放买入还是卖出都行但必须一致714题“买卖股票的最佳时机含手续费”每次交易要付固定手续费fee。核心决策点只有一个手续费什么时候从利润里扣除。两种主流写法卖出时扣费买入时只花prices[i]卖出时到账prices[i] - fee。买入时扣费买入时多花fee卖出时正常到账prices[i]。两种写法最终结果完全一样因为每笔交易只会扣一次费用扣在利润的哪一端不影响净收益。但一定要保持一致不能这边初始化按买入扣费那边转移又在卖出扣一次那就等于扣了两次。我习惯用“卖出时扣费”因为更符合直觉买入就是资金流出卖出就是资金流入手续费在流入时直接扣除不容易漏。4.2 卖出扣费版本的完整代码class Solution { public: int maxProfit(vectorint prices, int fee) { int n prices.size(); if (n 0) return 0; // 0: 空仓 1: 持有 vectorvectorint dp(n, vectorint(2, 0)); dp[0][0] 0; dp[0][1] -prices[0]; for (int i 1; i n; i) { // 空仓继续空仓或者从持有状态卖出并扣手续费 dp[i][0] max(dp[i - 1][0], dp[i - 1][1] prices[i] - fee); // 持有继续持有或者从空仓状态买入 dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[n - 1][0]; } };如果选买入时扣费初始化和转移改成dp[0][1] -prices[0] - fee; 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] - fee);只要保证“每一笔交易只在买入或卖出其中一个环节扣费”结果就不会有偏差。4.3 大手续费时为什么也能自动“不交易”有一个非常容易忽略的细节如果fee设置得很大比如prices每天波动只有1块但手续费要10块最优策略是干脆不做任何交易。这个行为不需要特判DP会自然给出0。原因在于dp[i][0] max(dp[i-1][0], ...)里的dp[i-1][0]它代表“之前一直空仓”的利润0。只要每次卖出的净利润是负的max就会选择继续空仓最终答案回到0。我拿prices[1,5,2,8], fee3跑过最优是先1买5卖赚4-31再2买8卖赚6-33总4。如果只看局部第一笔1买2卖利润是-1会被DP自动跳过。这种“自动跳过亏损交易”的特性是股票DP和贪心的一个重要区别也解释了为什么这类题用DP比贪心更稳。4.4 变体讨论双边收费怎么办如果题目改成“买入和卖出各收一次手续费”本质上等价于每笔交易支付2fee。你只需要把卖出扣的fee改成2fee或者把买入扣和卖出扣同时保留逻辑完全一致。理解了这个等价关系面试时不管手续费怎么包装你都能立刻转化成已知模型。5. 三题连刷的复盘我发现股票DP的通用套路5.1 第一步永远先画状态转移图我发现无论题目怎么变动手写代码前花两分钟把状态图画出来比直接背公式高效得多。所谓“状态转移图”就是用箭头表示“今天结束时的状态A经过什么操作可以变成明天结束时的状态B”。以309为例三状态的完整转移关系是持有态可以什么都不做继续持有也可以卖出进入冷冻空仓态。冷冻态什么都不做下一天变成可买入空仓态。可买入空仓态可以什么都不做继续空仓也可以买入进入持有态。把这个图画出来转移方程就是照着箭头写的根本不需要死记。188的状态图则是一串交替的持有/空仓节点买入和卖出就是沿着这串节点向前走。5.2 第二步明确“当天结束后”的时间点所有状态定义都要统一到“第i天结束后”。这样第i天的操作只依赖第i-1天结束时的状态不会出现同一天内先买后卖、先卖后买的混乱。有人喜欢定义成“第i天操作前”也可以但转移方程会多出不少边界判断。统一用“结束后”这个时间点代码最干净复盘时也最容易对照状态图。5.3 第三步判断状态维度能否压缩188的状态数随k线性增长309和714则只需要3个或2个状态。能压缩的题目通常有一个共同特征第i天只依赖第i-1天的值不需要更早的历史。这时用几个变量或两行数组滚动即可。但我给个实际建议刷题初期先老老实实写二维数组把逻辑跑通滚动数组作为进阶优化后续再做。因为滚动数组踩的坑旧值覆盖比二维数组多得多尤其是309那道题搞错求值顺序直接就是WA排查起来还不好找。5.4 面试时怎么快速讲清楚这类DP如果面试现场遇到股票类DP我的讲解顺序是固定的先定义状态“dp[i][j]表示第i天结束后处于状态j的最大利润。状态j分别代表……”然后列出状态图“持有态可以从……转移来空仓态可以从……转移来。”最后说初始化“第0天的合法操作决定了初值第0天买入就是-prices[0]不操作就是0。”复杂度直接报O(n状态数)状态数通常只有2到3个188则是O(nk)。这样讲解面试官能立刻看出你是真懂还是背题。尤其是188能说清楚“奇数状态从空仓买入、偶数状态从持有卖出”这个规律比直接甩代码要有说服力得多。6. 踩坑记录刷这三题时最容易犯的错6.1 常见问题速查表刷完这三题我把容易翻车的点整理成了一张速查表题目典型错误原因解决办法188数组大小写成2k而不是2k1忘了状态0表示“从未交易”下标0~2k长度2k1188k没有min(k, n/2)超大k导致内存爆炸没意识到完整交易至少两天dp前先做k min(k, n/2)188第0天奇数状态全部用极小值把第二笔交易的“买入”初始化为不合法用-prices[0]初始化所有奇数状态309状态压缩时直接原地更新新值覆盖了旧值导致后一个状态拿到“今天”的数据先缓存前一天三个状态再更新309状态1和状态2的转移写反没搞清楚“今天卖出当天算冷冻”状态1只由“昨天持有今天卖出”产生714买入扣费和卖出扣费混用手续费扣了两次或漏扣统一只在一端扣费初始化与之对应714不交易时答案变成负数手续费大于利润时被迫卖出dp[i][0]从dp[i-1][0]继承天然规避6.2 我自己的刷题习惯我在刷这三题时习惯是先把状态转移图写在纸上再对照官方题解看自己的状态分类和题解是否一致。如果一致再自己写代码如果不一致我会先想明白为什么题解这么分而不是直接抄代码。三题连刷下来我最大的感受是股票DP真正难的不是转移公式而是“状态划分”这一步。状态划对了公式自己就会冒出来状态划错后面全乱。6.3 给新手的两个自测小技巧一个是在LeetCode提交前先用小的样例手算一遍。比如309用[1,2,3,0,2]这类官方示例714用[1,3,2,8,4,9], fee2这类带手续费但仍有利润的用例。如果答案能跟手算对上代码大概率没问题。另一个是检查边界n0或n1要直接返回0k0也要返回0。很多WA不是因为转移方程错而是边界条件没写。把这个习惯固化下来之后刷其他DP题也一样受益。7. 训练营第四十天我的刷题节奏与笔记整理除了这三道题本身我也想聊聊怎么在一个训练营的节奏里把它们真正消化掉。代码随想录的题单是把同一专题的题集中排布所以第四十天其实是最好的“归纳整理”时机。我的做法是上午先不看题解自己尝试写188卡住了就回去翻123的两笔交易写法找“从2到k”的共性下午做309和714重点对比它们和122的差异。晚上把三道题的状态定义、转移方程、边界条件抄在同一页笔记上用表格横向比较。这页笔记后来在我复习时帮了大忙比反复刷题效率高得多。对于第一次接触股票DP的读者我的建议是不要试图一天内完全理解所有细节。先能独立写出188的二维DP再给309加上第三个状态最后给714加上手续费每一步都跑通官方用例。这样拆开练第四十天这个节点才能真正把“股票系列”转化为自己的东西。最后分享一个小技巧把三道题的状态定义压缩成一句话——“先想清楚每天交易结束后有哪几种状态再画箭头最后写转移公式”。这句口诀我后来在面试里用过好几次都能很快理清思路。股票DP并没有传说中那么玄它只是把“状态复用”这件事做到了极致而已。