我最早刷到“Best Time to Buy and Sell Stock”这道题时觉得不过是求个最大差值五分钟写完就划走了。后来在面试题单里连续碰到它的各种变体——冷冻期、手续费、限定交易次数——才发现这个系列根本就是一套状态机入门课程。它在力扣热题100和各大刷题攻略里基本是必刷项也是很多人从“背DP模板”到“真正理解状态转移”的转折点。这篇文章不会只丢给你代码我会从单次交易一路推到最多K次交易把这系列六道题的套路掰开揉碎。适合正在刷力扣准备算法面试的朋友也适合看完题解却始终串不起来的人。1. 单次交易的最优解从暴力枚举到一遍扫描的思维跃迁1.1 暴力法先确认答案长什么样先定义问题给定数组pricesprices[i]表示第 i 天的价格只能买卖一次先买后卖求最大利润。最直接的想法是枚举买入日 i 和卖出日 j要求 i j利润就是prices[j] - prices[i]取最大即可。def max_profit_brutal(prices): n len(prices) ans 0 for i in range(n): for j in range(i 1, n): ans max(ans, prices[j] - prices[i]) return ans复杂度 O(n²)能过小数据但力扣上 n 可以到 10^5这个方案必然超时。暴力法本身不是终点它的价值在于帮我们确认了两件事答案至少是 0不交易就没有利润而且必须满足买入日在卖出日之前。1.2 从“最大差值”到“维护历史最低点”既然枚举所有买入日太贵换个思路当我站在第 j 天想要卖出时最优的买入日一定是prices[0..j-1]里价格最低的那一天。因为卖出价格固定为prices[j]买入价格越低利润越高。所以只需要从头到尾扫一遍同时维护“当前遇到过的最低价格”每天计算一次潜在利润更新全局最大值。def max_profit(prices): min_price float(inf) ans 0 for price in prices: min_price min(min_price, price) # 更新历史最低买入价 ans max(ans, price - min_price) # 用今天的价格尝试卖出 return ans这段代码就是 121 题的标准解法时间 O(n)空间 O(1)。很多人背下来了但没想过为什么对。本质是一个贪心式的滚动决策每一天都在“用历史最低价买入、今天卖出”这个假设下计算虽然这个买入行为是提前发生的但它对应着一笔真实存在过的交易机会。因为最低价是在今天之前出现的所以先买后卖的约束天然满足。1.3 差分数组视角这题和最大子数组和是同一道题把相邻两天的价格差diff[i] prices[i] - prices[i-1]抽出来你会发现一个很有意思的等价关系单次交易的最大利润等于这个差分数组的最大连续子段和。例如prices [7, 1, 5, 3, 6, 4]差分数组是[-6, 4, -2, 3, -2]。如果我们在第 1 天价格1买入、第 4 天价格6卖出利润为 5对应的差分区间是[4, -2, 3]和正好是 5。中间那段价格为 3 的日子并不影响总利润它只是把你买入到卖出之间的价格波动全部累加起来了。想明白这一点你就发现了这个系列最关键的一条暗线“买卖股票最大利润”和“最大子数组和”在数学上是同一件事。121 题等价于求差分数组的最大子段和这也解释了为什么很多 Kadane 算法的例题会拿它当引子。写出来就是这样def max_profit_kadane(prices): ans 0 cur 0 for i in range(1, len(prices)): diff prices[i] - prices[i - 1] cur max(diff, cur diff) # 标准Kadane ans max(ans, cur) return ans这个版本和前面的“历史最低点”方法殊途同归但视角完全不同。前者是站在卖出的角度反推买入后者是把问题转化成连续价格的累积。我建议两个方法都亲手写一遍后面理解 122 题的多笔交易时你会感谢现在这个视角。2. 交易次数放开之后无限次交易与手续费问题的贪心失效2.1 104天只能买一次不这次可以买卖无数次122 题把限制放松为可以无限次交易但每天最多持有一股。很多人第一反应是“那我每天都买卖”显然不对因为跌的时候买卖是亏的。正确的贪心策略特别简单只要今天比昨天贵就在昨天买、今天卖。def max_profit_unlimited(prices): ans 0 for i in range(1, len(prices)): if prices[i] prices[i - 1]: ans prices[i] - prices[i - 1] return ans为什么这个贪心是对的因为交易没有次数限制也没有手续费每一段价格上升都可以被“切开”成独立的一次交易。价格从 1 涨到 5 再涨到 10你一次交易吃 9 的利润拆成两笔吃 (5-1)(10-5)9利润完全一样。反过来看差分数组这个策略就是在对每个正数差分求和负差分全部跳过。所以在无限次交易、零成本的设定下问题退化成了“对差分数组里所有正数求和”。2.2 手续费出现贪心立刻失效一个反例就够了714 题加了条件每笔交易需要付手续费fee。此时贪心策略“见涨就卖”不成立。看个例子prices [1, 5, 10]fee 3。贪心会分成两笔交易利润 (5-1-3) (10-5-3) 12 3但如果只做一笔利润 10-1-3 6明显更好。原因在于每笔交易有固定成本把一段完整上涨拆成多笔每拆一次就多付一次手续费。利润 总差价 - 交易次数×手续费贪心只盯着差价忽略了交易次数这个变量。这就不能只用一行求和了需要引入状态机。我先给出 714 的标准状态机解法因为它是整个系列承上启下的关键模型def max_profit_with_fee(prices, fee): n len(prices) if n 2: return 0 cash 0 # 不持有股票时的现金 hold -prices[0] # 持有股票时的现金 for i in range(1, n): cash max(cash, hold prices[i] - fee) # 今天卖出 hold max(hold, cash - prices[i]) # 今天买入 return cash注意cash和hold的更新顺序。如果用这两个变量实现滚动更新先更新cash用到的hold是昨天的持有状态这个没问题再更新hold用到的cash已经是更新后的今天状态了这其实允许了“今天卖出后再买入”的连续操作实际中代表换仓是合理且常见的。核心逻辑在于任何一天你都只有两种状态——手上有没有股票而每次状态切换付出了相应的代价买入付钱卖出扣手续费。状态机的骨架到这里已经有了“持有”和“不持有”这两个状态就是后面所有变体的地基。3. 冷冻期登场从两状态到三状态的必要性3.1 为什么“昨天卖出今天就不能买”会让两状态崩掉309 题在无限次交易基础上加了冷冻期卖出的第二天不能买入但第三天可以。直接套 714 的两状态会遇到一个隐蔽的问题cash状态里既包含“昨天没卖、今天可买”也包含“昨天刚卖、今天禁止买”。这两类情况在同一个状态里但未来行为完全不同强行压缩只会得到错误答案。卡通一点理解你可以把状态机想成一个动作游戏角色有三个姿态——蹲下持币可买、站立持股、跳跃冷却刚卖出。跳跃落地的瞬间不能立刻蹲下攻击必须等一个冷却帧。如果你用两个状态建模相当于把“跳跃冷却中”和“蹲下”合并了角色会不遵守规则直接发动攻击。3.2 状态转移表不持股、持股、卖出后冷却分解成三个状态第 i 天结束时dp[i][0]不持股且当前不处于冷冻期明天可以买dp[i][1]持股dp[i][2]不持股且今天刚卖出明天处于冷冻期转移关系如下今天状态从哪来转移公式不持股、可买(d0)昨天就不持有且可买 / 昨天刚卖出处于冷却dp[i][0] max(dp[i-1][0], dp[i-1][2])持股(d1)昨天持股不动 / 昨天不持股可买并买入dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])刚卖出(d2)昨天持股并卖出dp[i][2] dp[i-1][1] prices[i]写成滚动变量版本就是很多题解里短小精悍的样子def max_profit_with_cooldown(prices): n len(prices) if n 2: return 0 d0 0 # 不持股可买 d1 -prices[0] # 持股 d2 0 # 刚卖出冷却 for i in range(1, n): new_d0 max(d0, d2) new_d1 max(d1, d0 - prices[i]) new_d2 d1 prices[i] d0, d1, d2 new_d0, new_d1, new_d2 return max(d0, d2)你可能见过另一种写法用dp[i-2]来避免冷冻期dp[i][1] max(dp[i-1][1], dp[i-2][0] - prices[i])它的逻辑是“昨天如果不持有那昨天不可能是卖出日否则今天在冷冻期不能买”所以只能从i-2天的不持股状态买入。这个写法本身没错但三个状态的版本更直白状态之间的边界清清楚楚不会在写i-2下标时搞混边界条件。我建议面试手写时优先用三状态版本。4. 限制交易次数的真正难点188题的K维状态机4.1 最多两次交易先写出四状态再谈抽象123 题把交易次数限制成最多两次。网上最常见的写法是维护四个变量first_buy、first_sell、second_buy、second_sell。它的含义是“按时间顺序完成两笔交易”第二笔买入必须在第一笔卖出之后才有资金所以更新顺序有严格的依赖关系def max_profit_twice(prices): first_buy float(-inf) first_sell 0 second_buy float(-inf) second_sell 0 for price in prices: first_buy max(first_buy, -price) first_sell max(first_sell, first_buy price) second_buy max(second_buy, first_sell - price) second_sell max(second_sell, second_buy price) return second_sell这个四状态版本质就是 K2 的特例。你可以在纸上模拟一轮第一天first_buy变成负的当天价格second_buy因为之前first_sell0也变成负的当天价格相当于第一天就把两笔交易的买入都初始化好了。后面每一天价格上升时first_sell和second_sell同时变大价格下跌时first_buy和second_buy的损耗有限因为有前面交易利润兜底。跑一遍[3, 2, 6, 5, 0, 3]最终答案是 42买6卖0买3卖符合预期。4.2 推广到 K 次三维Dp的每一维都要想清楚188 题把“最多两次”推广成“最多 K 次”。如果你能理解 123 题的四状态那么 188 题只是把“两次”这个硬编码换成了一层循环。定义dp[i][k][0]第 i 天结束时已经完成了 k 次交易不持股的最大利润dp[i][k][1]第 i 天结束时已经完成了 k 次交易持股的最大利润这里有个容易引起争议的概念“完成一次交易”到底以买入还是卖出为标志我推荐按“卖出为完成”来定义因为利润只有卖出后才落袋后面代码会清晰很多。转移方程dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i]) # 第k笔交易在今天卖出后完成 dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) # 从k-1笔完成状态买入开启第k笔用“卖出算完成”的口径时买入是从k-1笔完成状态跳过来卖出则是从“持有中”跳到“完成 k 笔”。边界的初始化也值得多说一句dp[0][0][0]0dp[0][0][1]要设置成-inf或-prices[0]取决于你怎么处理第一天买入。为了统一我的做法是所有持股状态初始化为-inf然后单独处理第一天买入def max_profit_k(prices, k): n len(prices) if n 2 or k 0: return 0 k min(k, n // 2) # 重要剪枝交易次数超过天数一半没有意义 dp [[[0] * 2 for _ in range(k 1)] for _ in range(n)] for j in range(k 1): dp[0][j][0] 0 dp[0][j][1] -prices[0] # 第一天可以买入算持有了 for i in range(1, n): for j in range(1, k 1): dp[i][j][0] max(dp[i-1][j][0], dp[i-1][j][1] prices[i]) dp[i][j][1] max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]) return max(dp[n-1][j][0] for j in range(k 1))k min(k, n // 2)这个剪枝是我特别想提醒的。因为一次完整的买卖至少需要两天K 大于 n/2 时真正有意义的交易次数上限就是 n/2继续保留大 K 白白增加时间和空间。力扣测试里出现过 K 特别大的用例不剪枝直接 TLE刷过的人都懂这个坑。4.3 空间压缩从三维到两行甚至一维三维 DP 中dp[i]只依赖dp[i-1]所以可以用滚动数组把第一维去掉。此时内部顺序要特别注意内层循环必须从大到小更新交易次数防止第 i 天的数据覆盖掉第 i-1 天的数据。类似 01 背包的更新顺序问题def max_profit_k_scroll(prices, k): n len(prices) if n 2 or k 0: return 0 k min(k, n // 2) dp0 [0] * (k 1) # 不持股已完成j笔 dp1 [-float(inf)] * (k 1) # 持股 for price in prices: for j in range(k, 0, -1): dp0[j] max(dp0[j], dp1[j] price) # 卖出完成第j笔 dp1[j] max(dp1[j], dp0[j-1] - price) # 买入开始第j笔 # j0的持股没有意义且必须保持-inf return max(dp0)这里倒序更新是为了让dp0[j-1]和dp1[j]都是“之前天数”的状态不会被本轮刚更新的值污染。空间从 O(nK) 压到 O(K)复杂度变成 O(K)。对于 K 在几百到几千之间的输入这种压缩不是锦上添花而是必须的。5. 面试追问环节边界、复杂度和状态机的统一视角5.1 六道题一张表把套路和复杂度都记住如果你准备面试我建议把下面这张表默写出来。它涵盖了这个系列最常见的追问力扣题号核心限制状态数量时间复杂度空间复杂度121只能买卖一次1维扫描O(n)O(1)122无限次交易贪心/两状态O(n)O(1)714无限次手续费两状态O(n)O(1)309无限次冷冻期三状态O(n)O(1)123最多两次四状态O(n)O(1)188最多K次K维状态机O(nK)O(K)5.2 面试里一定会被追问的四个“所以呢”如果 K 大于 n/2 会怎样直接退化成 122 题的贪心。因为交易次数足够多时手续费降低到零或没有冷冻期理论上能把每个上升段都吃掉K 的上限失去意义。空数组和单元素数组怎么处理返回 0。没有第二个价格任何交易都没有利润所有解法开头都应判定n 2返回 0。全是降序的价格怎么办不交易利润为 0。历史最低价不断更新price - min_price永远是负数或 0兜底答案 0 正确。这道题和“最大子数组和”到底什么关系121 题是求差分数组的最大子段和122 题是求差分数组中所有正数之和188/309/714 则是在差分数组基础上施加交易次数、冷却、成本约束的状态机变体。你能在面试中说清这层关系比背十篇题解都加分。5.3 边界用例自测清单写完全部解法之后我建议用这个清单自我检查prices [] - 0 prices [1] - 0 prices [5,4,3,2,1] - 0全降序 prices [1,2,3,4,5] - 121:4, 122:4, 714(fee上涨):4 prices [3,2,6,5,0,3], k2 - 4 prices [1,5,10], fee3 - 6不是3 prices [1,2,3,0,2], cool - 31买3卖 或 0买2卖这些用例覆盖了最容易出错的三类情况数组太短、全降序、以及“拆分交易会吃亏”的场景。6. 我刷这个系列踩过的坑以及一点总结第一个坑是初始化。121 题如果把最小价格初始化为 0那么全正数价格第一天就会算出负数利润并污染答案。必须初始化为float(inf)。第二个坑发生在 309 题我一开始试图用两状态加i-2绕冷冻期结果数组下标越界没处理好后来改成三状态一次性写对。第三个坑在 188 题滚动数组里交易次数的循环顺序写成了正序导致同一天内重复买入多次算出来的答案离谱地偏大。这三次翻车让我意识到状态机 DP 的难点从来不是“写出转移方程”而是把“状态”的含义界定清楚然后靠初始化和更新顺序把边界钉死。如果只保留一个心得我会说这个系列所有题都可以归为“在每一天结束时记录你处于什么状态、完成了多少笔交易”然后枚举当天能做的动作持有、卖出、买入、休息。121 是只有一个状态的廉价版122 是直接把正收益累加714 和 309 分别往状态里加了成本和冷却123 和 188 则多加了一个“交易次数”维度。公式框架永远是dp[i][状态][交易次数] max(什么都不做, 切换状态带来的收益)。最后分享一个我练手时的习惯。拿到新题当天先只写 121 的最优解和 309 的三状态解作为基准再花十分钟把 122 的贪心写成状态机版本体会“为什么贪心可以DP 也可以”。这两个动作做完整个系列的模式基本就烂熟于心了。以后再遇到股票题的魔改——比如“必须隔一天才能卖”“允许卖空”“加上涨跌幅限制”——至少第一反应不会是背公式而是知道该往状态机里加什么维度。