今天接着刷代码随想录算法训练营第四十天内容是三道买卖股票系列的变式题188买卖股票的最佳时机IV、309最佳买卖股票时机含冷冻期、714买卖股票的最佳时机含手续费。这三道题放在一起很有讲究它们把基础的股票动态规划又向外推了一大步一个加了交易次数限制一个加了冷却期约束一个加了手续费成本。对训练营刷到这里的人来说前几天的121、122、123应该已经打下了底子今天这三道题的核心已经不是“会不会写状态转移”而是能不能把状态设计想清楚。很多人在刷这三道题时最大的感受是公式看着都能懂一关掉题解自己写就翻车。原因在于买卖股票这类题目的状态定义高度抽象尤其是188这种带k次限制的题目状态数量直接翻倍初始化也容易出问题。这篇博客就按我自己的刷题思路把这三道题从状态设计、递推推导到滚动数组优化、常见坑位完整拉一遍希望能给正在卡这些题的同学一点参考。1. 三道题为什么值得放在一起刷先说结论121、122、123三题是“单次买卖、无限买卖、两次买卖”到了188、309、714约束条件就不再是“次数”这一个维度了。188是把123推广到“最多k次”考验的是能不能用统一的状态下标把交易次数编码进去309引入冷冻期相当于在“卖出”和“下一次买入”之间强行插入一个冷却时间714则是在每次交易利润中固定扣掉一笔手续费让“是不是值得卖”变成了一个需要考虑成本的问题。这三道题放在第四十天这个时间点实际上是动态规划专题里“状态机DP”的一次集中训练。所谓状态机DP通俗讲就是把一笔钱在账户里的形态拆成“持有股票”和“持有现金”这两种状态再把题目里的限制条件转化成状态之间的转移规则。所有股票类题目本质上都是在同一个骨架下改状态数量和转移边。这三道题一刷完再回去看121、122、123你会觉得之前那些特判都是某种更通用模型的简化版。所以这篇文章我不会只贴题解代码而是把每一步状态为什么要这么设计、初始化为什么是那串数字、滚动数组为什么顺序要对尽量都说清楚。2. 188. 买卖股票的最佳时机IV把k次交易拆成2k个状态这一题几乎所有人第一反应都是123题最多两笔交易我用四个状态硬编码那k笔交易我是不是得循环建状态思路对但实现上有几个细节非常容易被忽略。2.1 为什么k次交易不能直接套用贪心无限次交易的122题可以用贪心因为每一段上涨的利润都可以独立收割不用记录交易次数。但一旦限定了“最多k笔”贪心就失效了你没法判断当前这一笔卖出之后剩余的交易次数还够不够覆盖后面更大的涨幅。所以必须用动态规划而且状态里必须携带“已经完成了多少笔交易”的信息。最简单粗暴的做法是dp[i][j][t]三维分别表示天数、持股状态、已完成交易次数但这样代码写起来啰嗦内存也浪费。188题的经典做法是用下标本身来编码交易次数。2.2 状态设计奇数位持有偶数位空仓我直接用一维数组解释因为理解了它二维数组只是多了天数下标而已。设dp[j]表示当前天数结束后的某个状态j的取值范围是0到2kj 0空仓且一笔交易都没做过j 1持有股票且这是第一笔交易的买入阶段j 2空仓且已经完成第一笔交易j 3持有股票且这是第二笔交易的买入阶段j 4空仓且已经完成第二笔交易以此类推规律非常明显奇数下标代表“当前持有股票”偶数下标代表“当前空仓”而下标数值刚好编码了已经进行到第几次交易。j 2k是最终状态即完成k笔交易后的最大现金。这个设计的巧妙之处在于不需要额外开一个维度去记录交易次数交易次数被隐含在状态下标里。2.3 递推公式的完整推导对于每个新的一天价格price[i]到来后我们要决定“保持原状”还是“从上一状态转换过来”。先看奇数下标j持有状态dp[j] max(dp[j], dp[j - 1] - price[i])dp[j]保持原值表示昨天就持有今天继续持有dp[j - 1] - price[i]表示昨天处于空仓状态已完成上一次卖出今天买入进入持有状态再看偶数下标j空仓状态dp[j] max(dp[j], dp[j - 1] price[i])dp[j]保持原值表示昨天就空仓今天继续空仓dp[j - 1] price[i]表示昨天持有股票今天卖出赚取差价后回到空仓状态注意一个细节j从0到2k依次递增j - 1一定是刚好的对偶状态。比如j2空仓j-11持有这是一对完整的“买入→卖出”路径。j4空仓j-13持有这是第二对。所以循环里不需要分类讨论第几笔交易只需要判断奇偶。2.4 初始化到底是什么意思第一天的初始化经常有人写错。第0天dp[0] 0空仓且什么都没做所有奇数下标dp[1] dp[3] dp[5] ... -price[0]所有偶数下标除了0dp[2] dp[4] ... 0为什么第二天还没到第二笔买入状态就设为-prices[0]因为可以理解为第一天先完成了一笔“买卖同价”的零利润交易然后又立刻买入。比如价格10先买入10再卖出10现金不变然后再买入10现金为-10这个操作完全合法且不影响利润。用它作为状态初值后续第二笔、第三笔交易才能正常转移。如果你把dp[3]初始化为极小值意味着强制认为第二天之前不可能有第二笔买入那遇到“第一天就大跌、第二天就大涨”的用例就会漏答案。最稳的做法就是奇数位统一初始化为-prices[0]。2.5 一维滚动数组和从后往前的遍历顺序二维写法空间是O(n*k)一维滚动可以压到O(k)。但有个关键点更新一维dp时必须从后往前遍历j。原因不复杂。比如更新dp[2]时需要用到dp[1]的“昨天”值如果j从小到大更新dp[1]已经被今天的price更新过了那dp[2]用的就是“今天买入后”的dp[1]相当于在一天之内连续做了“买入→卖出→再买入”虽然同价买卖的边距为0不会让答案变大但为了和二维递推严格对齐习惯上还是从大到小遍历保证每个状态引用的都是前一天旧值。完整代码class Solution { public int maxProfit(int k, int[] prices) { int n prices.length; if (n 0 || k 0) { return 0; } // 关键剪枝n天最多完成n/2次完整交易 k Math.min(k, n / 2); int[] dp new int[2 * k 1]; // 奇数位初始化为第一天的买入价 for (int j 1; j 2 * k; j 2) { dp[j] -prices[0]; } for (int i 1; i n; i) { for (int j 2 * k; j 1; j--) { if ((j 1) 1) { // 持有状态保持 或 从空仓买入 dp[j] Math.max(dp[j], dp[j - 1] - prices[i]); } else { // 空仓状态保持 或 从持有卖出 dp[j] Math.max(dp[j], dp[j - 1] prices[i]); } } } return dp[2 * k]; } }时间复杂度是O(n*k)空间是O(k)。2.6 k值的剪枝数学解释每天最多只能完成一笔买入加一笔卖出而一笔完整交易至少需要两天所以n天最多完成n/2次完整交易。题目给的k如果大于n/2其实可以剪枝为n/2否则dp数组浪费空间而且白白增加循环次数。这个剪枝不是可选项是性能优化里的必要一步。我一开始没剪枝在某些大k用例直接超时剪完立刻通过。3. 309. 最佳买卖股票时机含冷冻期三个状态比四个更好理解309这题刚上手的时候很容易把状态分成“持有”和“不持有”两个然后在卖出后加一天冷却。但实际上两个状态不够因为“不持有”分成了两种完全不同含义的情况处于冷却期不能买和不在冷却期可以买。所以正确做法是拆成三个状态。3.1 冷冻期如何改变状态图如果题目没有冷冻期持有和空仓两个状态互相转来转去就行。加了冷冻期以后从“卖出”这个动作出来必须先在“冷冻”状态停留一天才能回到“可买入”状态。也就是说状态转换图变成一条链表持有股票 → 卖出 → 冷冻期 → 可买入 → 买入 → 持有股票这也解释了为什么不能像122那样简单地贪心如果某一天刚卖出第二天即使出现更低价格也不能立刻买贪心的“回补”逻辑直接失效。3.2 三个状态的定义设dp[i][0]为第i天结束后持有股票的最大利润dp[i][1]为第i天结束后不持有股票且处于冷冻期的最大利润dp[i][2]为第i天结束后不持有股票且不在冷冻期的最大利润。这里最重要的主观提醒是“冷冻期”指的是卖出当天结束后开始计算第二天不能买入。所以处于dp[i][1]状态的人就是今天刚刚卖出明天被禁止买入。3.3 递推公式逐条看第一条dp[i][0] max(dp[i - 1][0], dp[i - 1][2] - prices[i])保持不变昨天就持有今天继续持有买入昨天不持有且不在冷冻期今天才能买入第二条dp[i][1] dp[i - 1][0] prices[i]这一条是直接赋值不是max。因为只有一种途径进入冷冻期昨天持有今天卖出。不存在“昨天冷冻期今天接着冷冻”的情况冷冻期只有一天。第三条dp[i][2] max(dp[i - 1][1], dp[i - 1][2])昨天处于冷冻期今天解除冷冻可以买入昨天就不在冷冻期今天继续保持可买入状态为什么必须要有这一条因为dp[i][1]只代表今天刚卖出的人如果昨天是冷冻期今天已经自动恢复成可买状态这个状态必须归属于dp[i][2]否则第二天买入时找不到正确的来源。3.4 初始化的细节处理初始化常见困惑就是dp[0][1]到底设多少。第一天结束时不可能处于冷冻期因为没有股票可卖但习惯上把它设为0。可以理解为第一天虚拟地做了一次不赚不亏的买卖然后进入冷冻期或者直接解释为“不可能状态设为0不会影响最终答案”。我更推荐一个严谨一点的说法dp[0][1]0等价于“买入且卖出同一支股票利润为0”这种虚拟状态不会污染后续max运算反而让代码简单。完整代码class Solution { public int maxProfit(int[] prices) { int n prices.length; if (n 0) { return 0; } int[][] dp new int[n][3]; dp[0][0] -prices[0]; dp[0][1] 0; dp[0][2] 0; for (int i 1; i n; i) { dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]); dp[i][1] dp[i - 1][0] prices[i]; dp[i][2] Math.max(dp[i - 1][1], dp[i - 1][2]); } return Math.max(dp[n - 1][1], dp[n - 1][2]); } }最后返回时不能取dp[n-1][0]因为最后一天还持有股票明显不是最优解。需要在“刚卖出处于冷冻期”和“空仓可买”两个状态里取最大值。3.5 空间压缩为三个滚动变量如果只想开O(1)空间可以用三个变量交替滚动。这里有个容易踩坑的点必须用临时变量保存旧值。int hold -prices[0]; int cool 0; int free 0; for (int i 1; i n; i) { int newHold Math.max(hold, free - prices[i]); int newCool hold prices[i]; int newFree Math.max(free, cool); hold newHold; cool newCool; free newFree; } return Math.max(cool, free);newFree不能直接用旧的free更新后再算newHold因为如果free先变成了“今天才解除冷冻”的状态那今天就不能再用来买入逻辑顺序上就乱了。这种细小的顺序问题在笔试里特别容易让人栽跟头建议手工模拟一遍就理解了。4. 714. 买卖股票的最佳时机含手续费贪心和DP都能通过714相比前两题其实更简单但它是三题里最适合练“把成本建模进状态”的题目。手续费带来一个显著变化有些看似上涨的小波段去掉手续费后反而亏钱所以不能无脑赚差价。4.1 手续费扣在哪一步更合理手续费可以设置在买入时也可以设置在卖出时。只要整道题统一只扣一次最终结果是一样的。习惯上放在卖出时更容易理解卖出后钱变多但每笔交易要扣除固定手续费。设置一个状态定义dp[i][0]第i天结束后持有股票的最大利润dp[i][1]第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] - fee)第一个式子表示保持持有或买入第二个式子表示保持空仓或卖出时扣手续费。4.2 DP写法class Solution { public int maxProfit(int[] prices, int fee) { int n prices.length; if (n 2) { return 0; } int[][] dp new int[n][2]; dp[0][0] -prices[0]; dp[0][1] 0; for (int i 1; i n; i) { dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]); dp[i][1] Math.max(dp[i - 1][1], dp[i - 1][0] prices[i] - fee); } return dp[n - 1][1]; } }这个写法是最稳妥的也不容易错。如果面试时间紧直接上DP版基本不会翻车。4.3 贪心解法的理解难度在于buy的更新规则714有一个比DP短很多的贪心写法我第一次看到时根本不敢信因为利润是拆成一段一段累加的。核心思路是用buy维护“当前买入成本含手续费”只要价格高于成本就卖出然后把buy更新为当前价格如果后续遇到更低的价格再重新设定买入成本。class Solution { public int maxProfit(int[] prices, int fee) { int n prices.length; if (n 2) { return 0; } int buy prices[0] fee; int profit 0; for (int i 1; i n; i) { if (prices[i] buy) { profit prices[i] - buy; buy prices[i]; } else if (prices[i] fee buy) { buy prices[i] fee; } } return profit; } }这个版本里buy第一次是“价格手续费”的买入门槛。当价格高于buy时卖出利润是prices[i] - buy但卖出后buy被更新成prices[i]而不是prices[i]fee。很多人不理解这一步为什么再次买入不收手续费了我的理解是每次真正卖出时手续费已经通过“prices[i] - buy”中的buy扣除了一次。卖出后更新buy为当前价相当于假设自己在卖出当天重新买入如果第二天继续上涨后续累积的利润是纯粹的上涨差价不需要再重复扣手续费。这样一段连续上涨的所有利润总和等于“最终卖价 - 最初买价 - 一次手续费”跟一笔完成交易的结果一致。如果遇到prices[i]fee比当前buy还便宜说明出现了一个明显更优的买入点这时更新buy为prices[i]fee相当于抛弃之前一段还没卖出的持仓重新挂一个新的买入单。这个贪心写法效率很高时间复杂度O(n)空间O(1)。但它的正确性依赖对buy更新的精确理解如果没吃透笔试现场容易把自己绕晕。我建议先写DP版保底等有时间再尝试贪心。4.4 两种解法怎么选DP版适用范围更广扩展性强比如后续如果再叠加冷冻期或交易次数限制DP版只需要改状态转移而贪心版基本要重写。贪心版胜在常数小、代码短理解透了在面试里能加分。我个人的习惯是如果面试官明确要最优时间空间再写贪心否则用DP。5. 三题对比、常见误区与通用套路三题刷完我试着把它们放在一张表里对比能更直观看到区别题目状态数量额外限制时间复杂度空间复杂度核心难点188 买卖股票IV2k1最多k笔交易O(n*k)O(k)用状态下标编码交易次数309 含冷冻期3卖出后隔一天才能买O(n)O(1)正确拆分“不持有”语义714 含手续费2每笔交易扣手续费O(n)O(1)手续费建模与贪心更新规则三题共同的内核是把资金形态抽象成“持有股票”和“持有现金”两类限制条件转成状态转移的边。188限制的是边的数量309限制的是“卖出到买入”边的延迟714则是给卖出边加了一个负权重。5.1 最容易踩的三个坑第一个坑是188不剪枝k值。k如果大于n/2dp数组长度会很大循环次数也翻倍在大数据用例下会超时。先用kMath.min(k, n/2)剪枝这是很多题解不会特意强调但很重要的细节。第二个坑是309的dp状态定义不清。如果把不持有笼统当一个状态买入时就分不清昨天是否在冷冻期导致错误答案。必须分成“冷冻期”和“可买”两个状态记住冷冻期只会停留一天dp[i][1]只能由卖出转移而来。第三个坑是714的滚动数组或贪心的更新时间不对。如果用一维DP滚动卖出状态先更新持有状态再更新会让同一天里卖出又买入产生额外的虚拟交易。稳妥做法是用临时变量存旧状态或者直接用二维数组。5.2 状态机DP的通用解题框架我把三道题放进同一个框架里代码随想录里也强调过动态规划五部曲这两者是统一的确定有哪些状态把所有可能的账户状态列全宁多勿少明确状态之间可以怎么转移画一下状态转移表哪些边存在、哪些边禁止根据转移表写递推公式初始化边界状态打印dp数组验证遇到新题先想这一步不要一上来套模板。比如以后遇到带n天冷却期、或者手续费随持有时间变化的变式只需要修改转移边和成本公式其他框架完全不变。5.3 一点刷题体会之前刷123题的时候四状态硬编码让我觉得股票DP是道“背模板题”但188一出来模板瞬间不够用了。真正帮到我的不是背公式而是把状态图画出来标注哪条边能走哪条边不能走再去写递推。309和714都是在画图之后一下就通了。如果你现在也在训练营刷到这里建议别急着把所有题解背下来先花十分钟在这三道题的状态图上画一画尤其是309那个三状态闭环画完再写代码会顺手很多。最后再说一个小技巧提交不过先别急着看题解把dp数组打出来逐行对比第一天的初始化有没有异常很多时候答案就藏在初始化的数字里。