LeetCode 188 题是我刷股票系列时印象最深的一道标题里的 day46 说明已经刷了一个半月前面 121、122、123 都顺利过了结果卡在“最多 k 笔交易”这个泛化版本上。很多人的反应和我一样123 题最多两笔已经要小心处理了现在把 2 换成参数 k就彻底不知道状态该怎么写了。这道题的核心是动态规划而且不是简单的区间 DP需要用状态机来拆解“持股 / 空仓”和“交易次数”两个维度。它属于 LeetCode 股票系列里最通用的一版解法把 121 的一次交易、122 的无限次交易、123 的两次交易全都能统一进来。理解透这一题后面 309 的冷冻期、714 的手续费都只是在这套状态机上加条件。这篇主要写给正在刷动态规划、尤其是做到 188 觉得无从下手的同学。我会从状态定义说起把完整的三维 DP 拆开讲清楚再给出可以直接抄的一维滚动优化版本最后必须聊一聊k n/2这个关键剪枝条件。整个过程会穿插我自己踩过的坑比如 buy 数组初始化成 0 会算出来离谱利润、交易次数语义没对齐导致转移方程式全反这些细节在题解里很少有人单独拿出来说。1. 这个题目难在哪交易次数和持股状态缠在一起先说为什么 188 题能劝退一批人。股票系列前面的题大家都熟121 只能买卖一次遍历一遍记最低点就行122 不限次数把所有上涨段加起来就完事123 最多两笔最笨的办法是枚举第一次卖出的位置把数组切成两段分别算 121。但这些思路到了 188 全部失效因为 k 是个参数可能很大也可能很小你不能手工枚举分割点。1.1 股票系列从 121 到 714 的递进关系我把这个系列整理过一张表方便看到每道题的定位题号约束核心思路121只能买卖一次一次遍历维护最低价122不限交易次数贪心累加所有正差价123最多两笔两次动态规划 / 状态机188最多 k 笔通用状态机k 是参数309不限次数 卖掉后有冷冻期状态机加一天维度714不限次数 每笔扣手续费状态机卖出时扣费看这张表就明白188 是整个系列的“总纲”。121 和 122 是特例中的特例123 是 k2 的固定写法而 188 把 k 泛化之后你没法再靠“左边一段右边一段”这种技巧性做法必须回到模型本身。1.2 贪心在 188 为什么失效状态机为什么有效122 题用贪心能过是因为它不限制交易次数所有上涨区间都可以独立变现。但 188 限定了最多 k 笔如果 k2而股价涨了 5 段你就只能挑利润最大的两段或者把一些段合并起来吃掉更大利润。这是典型的全局决策问题贪心只看局部是不行的。状态机模型擅长处理这类问题它把“当前是否持有股票”和“已经用掉了多少次交易机会”拆成独立维度。第 i 天结束时你只可能处于两种状态要么手里有股票要么手里没有。有股票是一种命运没有股票是另一种命运而决策就是每天在“买入、卖出、不动”三个动作里选一个。配合交易次数这个维度就形成了一个状态转移的网格动态规划在这个网格上逐天推进。打个比方状态机像你在打牌手里有没有牌持股状态是一码事已经打出去几轮交易次数是另一码事。每轮你可以选择出牌、收牌、或过但你必须知道现在打到第几轮才能决定下一步怎么走。2. 状态定义把第几天、第几次、是否持股三个维度对齐三维 DP 的难点不在写代码而在搞清楚 dp 数组每个维度到底代表什么。尤其是 j 这个维度题解里有人用来表示“已经完成的交易次数”有人表示“已经开始的交易次数”两种定义会导致转移方程差一个下标代码写出来完全不同。2.1 我采用的状态定义与官方题解保持一致我写这道题用的定义是dp[i][j][0]表示前 i 天结束时已经进行了 j 次交易且当前不持有股票的最大利润dp[i][j][1]表示前 i 天结束时已经进行了 j 次交易且当前持有股票的最大利润。这里的关键是 j 的计数方式买入的那一刻算作一次“正在进行的交易”所以 j 会增加卖出的时候只是把这次交易结束掉j 不再增加。换句话说j 代表“已经启动的交易次数”而不是“已经完整做完的交易次数”。用真实场景走一遍第 1 天买入没有任何卖出记录这算 j1第 3 天卖出手里没有股票交易完成j 还是 1不变成 2。如果再买一次就变成 j2。这个口径一旦对齐后面所有转移都不会乱。2.2 状态转移方程的推导过程和计数细节有了定义转移方程就好推了。第 i 天不持有股票两种情况昨天就不持有今天什么都没做或者昨天持有今天把股票卖掉。写成式子dp[i][j][0] max(dp[i-1][j][0], dp[i-1][j][1] prices[i])注意这里 j 没有变化。昨天持有且“已经进行了 j 次交易”今天卖出交易次数依然是 j因为这笔交易在买入时已经计数了。第 i 天持有股票两种情况昨天就持有今天不动或者昨天不持有今天买入。买入会开启一次新交易所以 j 从 j-1 变成 jdp[i][j][1] max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])这个方程是最容易写错的地方。很多同学会写成dp[i-1][j-1][1]这就完全乱了。买入之前一定是不持股持股状态只能从[0]转移过来交易次数 j 是从j-1跳过来的因为这次买入消耗了一次机会。初始化和边界条件同样关键dp[0][0][0] 0第 0 天不持股、未交易正确dp[0][j][0] 0第 0 天不持股但“已进行 j 次交易”这在现实中不可能但因为不会影响后续 max 的结果保留 0 可以dp[0][j][1] -infinity第 0 天就持有股票这是不合法状态绝对不能给 0。如果给 0后续卖出时会凭空多出一份利润相当于股票白送。最终答案就是max(dp[n-1][j][0])j 从 0 到 k。注意必须取所有 j 的最大值因为题目说“最多 k 笔交易”不是“恰好 k 笔”可能只用 3 笔就达到最大利润没必要非要凑满 k 笔。3. 代码落地完整三维 DP 与一维滚动写法理解三维 DP 之后代码实现反而简单。但 LeetCode 上 k 可以到 10^9直接开n * k * 2的数组会爆内存所以实际提交时基本都写一维滚动版本。3.1 先看一维滚动版本的正确形态用两个长度为 k1 的数组代替三维 DP 的第二和第三个维度buy[j]对应持有状态sell[j]对应空仓状态。遍历每一天价格时j 从 k 到 1 倒序更新class Solution: def maxProfit(self, k: int, prices: List[int]) - int: n len(prices) if n 2: return 0 if k n // 2: profit 0 for i in range(1, n): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit buy [float(-inf)] * (k 1) sell [0] * (k 1) for price in prices: for j in range(k, 0, -1): buy[j] max(buy[j], sell[j - 1] - price) sell[j] max(sell[j], buy[j] price) return sell[k]这段代码是我经过反复验证后最终稳定使用的版本下面逐行拆开讲一遍。3.2 初始化为什么必须用负无穷buy数组初始化为float(-inf)这是整个代码最容易被忽略的细节。如果初始化成 0第一次更新buy[j]时会得到max(0, 0 - price)这相当于你手里凭空有了一笔“0 成本持仓”的收益等后面卖出时利润会被大幅高估。但初始化为-inf后只有真正从sell[j-1]的状态买入buy[j]才会变成合法值。如果用-prices[0]初始化也能通过测试。它的含义是“强制在第 0 天买入”相当于省略了第 0 天的循环。但我倾向于-inf因为它在语义上更严格地排除了非法状态也方便扩展到其他股票题目。3.3 为什么循环 j 要倒序这是一个面试高频追问点。在更新buy[j]时需要用到上一轮状态中的sell[j-1]。如果 j 正序从 1 到 k那么当buy[j]执行到一半时sell[j-1]已经被这一轮的price更新过导致当天的价格被重复使用相当于允许了“同一天卖出再买入”。虽然“同一天卖出再买入”在实际中收益就是 0并不一定破坏最优解但严谨的状态机要求每轮从昨天的状态出发。倒序更新后j更大j-1不会先被更新buy[j]拿到的sell[j-1]一定是前一天的值整个转移干净利落也方便和面试官讲清楚原理。另外注意更新顺序buy[j]先更新然后sell[j]才能用buy[j]的新值。因为当天买入再当天卖出等价于什么都没发生不会产生额外收益所以在一次循环内先更新 buy 再更新 sell 是安全的。这个顺序颠倒会得到错误结果。4. 边界条件剪枝k n//2 时必须走贪心第一次写 188 题时我没加任何剪枝直接把二维数组开到k1结果在 k 很大时直接内存溢出。后来才意识到k和n之间存在一个硬关系一笔完整的交易至少需要两天一天买入一天卖出。4.1 为什么 n 天最多只能完成 n//2 笔交易这是一个很容易理解但很多人没意识到的结论。如果只有 2 天你最多买入 1 次、卖出 1 次做成一笔交易如果只有 4 天最多两笔第一笔在第 1 天买第 2 天卖第二笔在第 3 天买第 4 天卖。所以交易次数的上限是n // 2。当 k 已经大于等于这个上限时k 的约束实际上消失了。无论 k 是 5 还是 1000最多只能完成 n//2 笔那不如直接允许无限次交易。无限次交易的最优解就是用贪心累积所有上涨差值这个结论在 122 题里已经证明过。4.2 剪枝前后的复杂度变化未剪枝版本的空间和时间复杂度都是 O(n * k)当n1000k10^9时不仅buy、sell数组开不出来时间也完全不可接受。剪枝之后最坏情况复杂度降为 O(n)用一次遍历累加正差价就结束快得多。LeetCode 的官方测试数据里刻意包含 k 很大的场景不剪枝直接提交会 TLE 或 MLE。我最初因为没做这个判断一个 case 都过不了加上剪枝后秒过。虽然这道题名义上是动态规划题但第一道关卡其实是这个小小的数学观察。5. 用 188 的框架去套其他股票题把这套状态机吃透之后股票系列其他题目基本就是改一行代码的事。5.1 123 题就是 k2 的特例如果你已经写了 188 的通用版本123 题直接调用maxProfit(2, prices)就行。这也是我建议先做 188 再做 123 的原因先掌握通用解法特例只是参数不同。反过来先做 123 再做 188反而容易陷入“专门为两笔交易写状态”的思维定式。5.2 714 题手续费、309 题冷冻期怎么扩展714 题每笔交易要扣手续费最简单的方式是在卖出时扣掉 feefor j in range(k, 0, -1): buy[j] max(buy[j], sell[j - 1] - price) sell[j] max(sell[j], buy[j] price - fee)309 题要求卖出后第二天不能买需要多记录一个“冷冻期”状态本质是在状态机里加一个“第 i-1 天刚卖出”的维度。基本思路不变只是将二维状态扩展成三态空仓、持仓、冷冻期。5.3 我总结的一个通用刷题流程遇到股票 DP 题我现在的做法是固定的先确认有几个状态是否持股、是否冷冻期、是否有持仓限制再确认交易次数维度怎么计数买入时1 还是卖出时1最后画一个小表格手推 3 天数据验证转移方程确认无误后写一维滚动版本。这套流程能覆盖 80% 的股票类动态规划题目188 是练熟这套流程最合适的题。这道题我实际刷了三遍才有把握不看题解写出来。第一遍卡在 j 的语义第二遍卡在 buy 数组初始化成 0 导致样例全错第三遍才把倒序循环和 k 剪枝讲明白。如果能给刚开始刷这道题的人一个建议别急着看代码先把dp[i][j][0]和dp[i][j][1]的定义用嘴说清楚能从第 1 天推演到第 3 天再动手写效率会高很多。
LeetCode 188 股票买卖最佳时机 IV：状态机动态规划全解析
LeetCode 188 题是我刷股票系列时印象最深的一道标题里的 day46 说明已经刷了一个半月前面 121、122、123 都顺利过了结果卡在“最多 k 笔交易”这个泛化版本上。很多人的反应和我一样123 题最多两笔已经要小心处理了现在把 2 换成参数 k就彻底不知道状态该怎么写了。这道题的核心是动态规划而且不是简单的区间 DP需要用状态机来拆解“持股 / 空仓”和“交易次数”两个维度。它属于 LeetCode 股票系列里最通用的一版解法把 121 的一次交易、122 的无限次交易、123 的两次交易全都能统一进来。理解透这一题后面 309 的冷冻期、714 的手续费都只是在这套状态机上加条件。这篇主要写给正在刷动态规划、尤其是做到 188 觉得无从下手的同学。我会从状态定义说起把完整的三维 DP 拆开讲清楚再给出可以直接抄的一维滚动优化版本最后必须聊一聊k n/2这个关键剪枝条件。整个过程会穿插我自己踩过的坑比如 buy 数组初始化成 0 会算出来离谱利润、交易次数语义没对齐导致转移方程式全反这些细节在题解里很少有人单独拿出来说。1. 这个题目难在哪交易次数和持股状态缠在一起先说为什么 188 题能劝退一批人。股票系列前面的题大家都熟121 只能买卖一次遍历一遍记最低点就行122 不限次数把所有上涨段加起来就完事123 最多两笔最笨的办法是枚举第一次卖出的位置把数组切成两段分别算 121。但这些思路到了 188 全部失效因为 k 是个参数可能很大也可能很小你不能手工枚举分割点。1.1 股票系列从 121 到 714 的递进关系我把这个系列整理过一张表方便看到每道题的定位题号约束核心思路121只能买卖一次一次遍历维护最低价122不限交易次数贪心累加所有正差价123最多两笔两次动态规划 / 状态机188最多 k 笔通用状态机k 是参数309不限次数 卖掉后有冷冻期状态机加一天维度714不限次数 每笔扣手续费状态机卖出时扣费看这张表就明白188 是整个系列的“总纲”。121 和 122 是特例中的特例123 是 k2 的固定写法而 188 把 k 泛化之后你没法再靠“左边一段右边一段”这种技巧性做法必须回到模型本身。1.2 贪心在 188 为什么失效状态机为什么有效122 题用贪心能过是因为它不限制交易次数所有上涨区间都可以独立变现。但 188 限定了最多 k 笔如果 k2而股价涨了 5 段你就只能挑利润最大的两段或者把一些段合并起来吃掉更大利润。这是典型的全局决策问题贪心只看局部是不行的。状态机模型擅长处理这类问题它把“当前是否持有股票”和“已经用掉了多少次交易机会”拆成独立维度。第 i 天结束时你只可能处于两种状态要么手里有股票要么手里没有。有股票是一种命运没有股票是另一种命运而决策就是每天在“买入、卖出、不动”三个动作里选一个。配合交易次数这个维度就形成了一个状态转移的网格动态规划在这个网格上逐天推进。打个比方状态机像你在打牌手里有没有牌持股状态是一码事已经打出去几轮交易次数是另一码事。每轮你可以选择出牌、收牌、或过但你必须知道现在打到第几轮才能决定下一步怎么走。2. 状态定义把第几天、第几次、是否持股三个维度对齐三维 DP 的难点不在写代码而在搞清楚 dp 数组每个维度到底代表什么。尤其是 j 这个维度题解里有人用来表示“已经完成的交易次数”有人表示“已经开始的交易次数”两种定义会导致转移方程差一个下标代码写出来完全不同。2.1 我采用的状态定义与官方题解保持一致我写这道题用的定义是dp[i][j][0]表示前 i 天结束时已经进行了 j 次交易且当前不持有股票的最大利润dp[i][j][1]表示前 i 天结束时已经进行了 j 次交易且当前持有股票的最大利润。这里的关键是 j 的计数方式买入的那一刻算作一次“正在进行的交易”所以 j 会增加卖出的时候只是把这次交易结束掉j 不再增加。换句话说j 代表“已经启动的交易次数”而不是“已经完整做完的交易次数”。用真实场景走一遍第 1 天买入没有任何卖出记录这算 j1第 3 天卖出手里没有股票交易完成j 还是 1不变成 2。如果再买一次就变成 j2。这个口径一旦对齐后面所有转移都不会乱。2.2 状态转移方程的推导过程和计数细节有了定义转移方程就好推了。第 i 天不持有股票两种情况昨天就不持有今天什么都没做或者昨天持有今天把股票卖掉。写成式子dp[i][j][0] max(dp[i-1][j][0], dp[i-1][j][1] prices[i])注意这里 j 没有变化。昨天持有且“已经进行了 j 次交易”今天卖出交易次数依然是 j因为这笔交易在买入时已经计数了。第 i 天持有股票两种情况昨天就持有今天不动或者昨天不持有今天买入。买入会开启一次新交易所以 j 从 j-1 变成 jdp[i][j][1] max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])这个方程是最容易写错的地方。很多同学会写成dp[i-1][j-1][1]这就完全乱了。买入之前一定是不持股持股状态只能从[0]转移过来交易次数 j 是从j-1跳过来的因为这次买入消耗了一次机会。初始化和边界条件同样关键dp[0][0][0] 0第 0 天不持股、未交易正确dp[0][j][0] 0第 0 天不持股但“已进行 j 次交易”这在现实中不可能但因为不会影响后续 max 的结果保留 0 可以dp[0][j][1] -infinity第 0 天就持有股票这是不合法状态绝对不能给 0。如果给 0后续卖出时会凭空多出一份利润相当于股票白送。最终答案就是max(dp[n-1][j][0])j 从 0 到 k。注意必须取所有 j 的最大值因为题目说“最多 k 笔交易”不是“恰好 k 笔”可能只用 3 笔就达到最大利润没必要非要凑满 k 笔。3. 代码落地完整三维 DP 与一维滚动写法理解三维 DP 之后代码实现反而简单。但 LeetCode 上 k 可以到 10^9直接开n * k * 2的数组会爆内存所以实际提交时基本都写一维滚动版本。3.1 先看一维滚动版本的正确形态用两个长度为 k1 的数组代替三维 DP 的第二和第三个维度buy[j]对应持有状态sell[j]对应空仓状态。遍历每一天价格时j 从 k 到 1 倒序更新class Solution: def maxProfit(self, k: int, prices: List[int]) - int: n len(prices) if n 2: return 0 if k n // 2: profit 0 for i in range(1, n): if prices[i] prices[i - 1]: profit prices[i] - prices[i - 1] return profit buy [float(-inf)] * (k 1) sell [0] * (k 1) for price in prices: for j in range(k, 0, -1): buy[j] max(buy[j], sell[j - 1] - price) sell[j] max(sell[j], buy[j] price) return sell[k]这段代码是我经过反复验证后最终稳定使用的版本下面逐行拆开讲一遍。3.2 初始化为什么必须用负无穷buy数组初始化为float(-inf)这是整个代码最容易被忽略的细节。如果初始化成 0第一次更新buy[j]时会得到max(0, 0 - price)这相当于你手里凭空有了一笔“0 成本持仓”的收益等后面卖出时利润会被大幅高估。但初始化为-inf后只有真正从sell[j-1]的状态买入buy[j]才会变成合法值。如果用-prices[0]初始化也能通过测试。它的含义是“强制在第 0 天买入”相当于省略了第 0 天的循环。但我倾向于-inf因为它在语义上更严格地排除了非法状态也方便扩展到其他股票题目。3.3 为什么循环 j 要倒序这是一个面试高频追问点。在更新buy[j]时需要用到上一轮状态中的sell[j-1]。如果 j 正序从 1 到 k那么当buy[j]执行到一半时sell[j-1]已经被这一轮的price更新过导致当天的价格被重复使用相当于允许了“同一天卖出再买入”。虽然“同一天卖出再买入”在实际中收益就是 0并不一定破坏最优解但严谨的状态机要求每轮从昨天的状态出发。倒序更新后j更大j-1不会先被更新buy[j]拿到的sell[j-1]一定是前一天的值整个转移干净利落也方便和面试官讲清楚原理。另外注意更新顺序buy[j]先更新然后sell[j]才能用buy[j]的新值。因为当天买入再当天卖出等价于什么都没发生不会产生额外收益所以在一次循环内先更新 buy 再更新 sell 是安全的。这个顺序颠倒会得到错误结果。4. 边界条件剪枝k n//2 时必须走贪心第一次写 188 题时我没加任何剪枝直接把二维数组开到k1结果在 k 很大时直接内存溢出。后来才意识到k和n之间存在一个硬关系一笔完整的交易至少需要两天一天买入一天卖出。4.1 为什么 n 天最多只能完成 n//2 笔交易这是一个很容易理解但很多人没意识到的结论。如果只有 2 天你最多买入 1 次、卖出 1 次做成一笔交易如果只有 4 天最多两笔第一笔在第 1 天买第 2 天卖第二笔在第 3 天买第 4 天卖。所以交易次数的上限是n // 2。当 k 已经大于等于这个上限时k 的约束实际上消失了。无论 k 是 5 还是 1000最多只能完成 n//2 笔那不如直接允许无限次交易。无限次交易的最优解就是用贪心累积所有上涨差值这个结论在 122 题里已经证明过。4.2 剪枝前后的复杂度变化未剪枝版本的空间和时间复杂度都是 O(n * k)当n1000k10^9时不仅buy、sell数组开不出来时间也完全不可接受。剪枝之后最坏情况复杂度降为 O(n)用一次遍历累加正差价就结束快得多。LeetCode 的官方测试数据里刻意包含 k 很大的场景不剪枝直接提交会 TLE 或 MLE。我最初因为没做这个判断一个 case 都过不了加上剪枝后秒过。虽然这道题名义上是动态规划题但第一道关卡其实是这个小小的数学观察。5. 用 188 的框架去套其他股票题把这套状态机吃透之后股票系列其他题目基本就是改一行代码的事。5.1 123 题就是 k2 的特例如果你已经写了 188 的通用版本123 题直接调用maxProfit(2, prices)就行。这也是我建议先做 188 再做 123 的原因先掌握通用解法特例只是参数不同。反过来先做 123 再做 188反而容易陷入“专门为两笔交易写状态”的思维定式。5.2 714 题手续费、309 题冷冻期怎么扩展714 题每笔交易要扣手续费最简单的方式是在卖出时扣掉 feefor j in range(k, 0, -1): buy[j] max(buy[j], sell[j - 1] - price) sell[j] max(sell[j], buy[j] price - fee)309 题要求卖出后第二天不能买需要多记录一个“冷冻期”状态本质是在状态机里加一个“第 i-1 天刚卖出”的维度。基本思路不变只是将二维状态扩展成三态空仓、持仓、冷冻期。5.3 我总结的一个通用刷题流程遇到股票 DP 题我现在的做法是固定的先确认有几个状态是否持股、是否冷冻期、是否有持仓限制再确认交易次数维度怎么计数买入时1 还是卖出时1最后画一个小表格手推 3 天数据验证转移方程确认无误后写一维滚动版本。这套流程能覆盖 80% 的股票类动态规划题目188 是练熟这套流程最合适的题。这道题我实际刷了三遍才有把握不看题解写出来。第一遍卡在 j 的语义第二遍卡在 buy 数组初始化成 0 导致样例全错第三遍才把倒序循环和 k 剪枝讲明白。如果能给刚开始刷这道题的人一个建议别急着看代码先把dp[i][j][0]和dp[i][j][1]的定义用嘴说清楚能从第 1 天推演到第 3 天再动手写效率会高很多。
