今天接着刷代码随想录算法训练营第四十天，内容是三道买卖股票系列的变式题：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到2k：

• j = 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一定是刚好的对偶状态。比如j=2空仓，j-1=1持有，这是一对完整的“买入→卖出”路径。j=4空仓，j-1=3持有，这是第二对。所以循环里不需要分类讨论第几笔交易，只需要判断奇偶。

2.4 初始化到底是什么意思

第一天的初始化经常有人写错。第0天：

• dp[0] = 0，空仓且什么都没做
• 所有奇数下标：dp[1] = dp[3] = dp[5] = ... = -price[0]
• 所有偶数下标（除了0）：dp[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限制的是边的数量，309限制的是“卖出到买入”边的延迟，714则是给卖出边加了一个负权重。

5.1 最容易踩的三个坑

第一个坑是188不剪枝k值。k如果大于n/2，dp数组长度会很大，循环次数也翻倍，在大数据用例下会超时。先用k=Math.min(k, n/2)剪枝，这是很多题解不会特意强调但很重要的细节。

第二个坑是309的dp状态定义不清。如果把不持有笼统当一个状态，买入时就分不清昨天是否在冷冻期，导致错误答案。必须分成“冷冻期”和“可买”两个状态，记住冷冻期只会停留一天，dp[i][1]只能由卖出转移而来。

第三个坑是714的滚动数组或贪心的更新时间不对。如果用一维DP滚动，卖出状态先更新，持有状态再更新，会让同一天里卖出又买入，产生额外的虚拟交易。稳妥做法是用临时变量存旧状态，或者直接用二维数组。

5.2 状态机DP的通用解题框架

我把三道题放进同一个框架里，代码随想录里也强调过动态规划五部曲，这两者是统一的：

1. 确定有哪些状态：把所有可能的账户状态列全，宁多勿少
2. 明确状态之间可以怎么转移：画一下状态转移表，哪些边存在、哪些边禁止
3. 根据转移表写递推公式
4. 初始化边界状态
5. 打印dp数组验证

遇到新题，先想这一步，不要一上来套模板。比如以后遇到带n天冷却期、或者手续费随持有时间变化的变式，只需要修改转移边和成本公式，其他框架完全不变。

5.3 一点刷题体会

之前刷123题的时候，四状态硬编码让我觉得股票DP是道“背模板题”，但188一出来，模板瞬间不够用了。真正帮到我的不是背公式，而是把状态图画出来：标注哪条边能走，哪条边不能走，再去写递推。309和714都是在画图之后一下就通了。

如果你现在也在训练营刷到这里，建议别急着把所有题解背下来，先花十分钟在这三道题的状态图上画一画，尤其是309那个三状态闭环，画完再写代码会顺手很多。最后再说一个小技巧：提交不过先别急着看题解，把dp数组打出来，逐行对比第一天的初始化有没有异常，很多时候答案就藏在初始化的数字里。