动态规划状态机巧解股票交易系列｜从一次交易到K笔-平芜编程栈

最近在力扣上面刷题，把Best Time to Buy and Sell Stock这个系列的股票交易问题完整过了一遍。以前总觉得这类题就是套几个公式，背一背状态转移就完事，直到自己动手推导、把边界case一个个踩过去，才意识到里面藏着动态规划从入门到进阶的一条非常典型的学习路径。

这个系列至少有六道题，从“只能交易一次”到“不限次数”，再到“最多K笔”“卖掉后要冷冻一天”“每笔还要扣手续费”，难度一点点往上叠。如果你刚好在刷力扣，或者准备算法面试，这套题几乎是绕不过去的。这篇文章我按自己的理解，把这系列题的核心思路、状态机建模、代码实现和常见坑都整理出来，希望能帮你省点时间。

1. 系列题目概览与核心需求拆解

我先把这一系列题目拢到一起看。最经典的是第 121 题，要求你只能做一笔交易，也就是一次买入一次卖出，求最大利润。紧接着 122 题，允许你无限次交易，但每次只能持有一股，相当于你可以多次低买高卖。第 123 题限制最多完成两笔交易，第 188 题则把限制泛化成最多 K 笔。309 题加了一个交易日冷却期：卖掉股票后，要隔一天才能再次买入。714 题则是每笔交易要扣一笔固定的手续费。

这些题目看似条件各不相同，但骨子里有两条主线：一是“低买高卖”的朴素逻辑，二是动态规划里的状态机思想。第一道题可能用一次遍历就能解，但你很难用它去套后面的复杂版本。而一旦你掌握了状态机的建模方式，整个系列的所有题目都可以归到同一个框架下，只是状态数量和转移条件不一样。所以我在下面会先从最笨的暴力枚举讲起，再一步步升级到通用DP模型。

1.1 从“一次交易”到“任意多次”的难度递进

拿 121 题来说，第一次做的人很容易想到：遍历每一天作为买入日，再遍历它后面的每一天作为卖出日，算差值，取最大。这就是暴力枚举，时间复杂度 O(n²)，在小数据规模下能过，但输入到十万级别就直接超时。于是你自然会想到用一次遍历记录历史最低价格，边走边算当前价格和历史最低价的差值，把复杂度降到 O(n)。

到了 122 题，限制变成可以无限次交易。这时有一个直觉：既然没有次数限制，那每一段上涨都值得吃满，把相邻两天价格差为正的部分全部加起来就是最大利润。这个解法很妙，但它和 121 题的思路完全不一样，容易让人怀疑自己是不是跳过了什么。如果你直接上手 DP，会发现“今天持有的状态”和“今天不持有的状态”是可以互相转移的，这样就引出了状态机。

123 题最多两笔交易，一下子把问题变复杂：你不能再简单地累加上升段，因为两笔交易之间必然存在一个分割点，你要避免把连续上涨区间拆成多笔，也要避免在下跌阶段反复交易。暴力做法是先枚举分割点，左边一次交易、右边一次交易，但这样重复计算很多，需要预处理好前缀和后缀最大值数组。这个做法思路清晰，但还不是最优雅的。

188 题把数量泛化到 K 笔，直接三维 DP：天数、已交易次数、是否持股。到这里，你就能真切感受到动态规划为什么适合这类问题，因为它把“在第 i 天，进行了 j 次交易，当前持有或未持有股票”的每个状态都记录下来，天然避免了枚举分割点的冗余。

1.2 为什么股票交易题是动态规划的绝佳入门

很多人学动态规划时被“最小路径和”“最长递增子序列”劝退，因为状态定义太虚拟，不直观。而股票题目里天然存在两个状态：持有现金还是持有股票。你要做的只是决定每天都操作：买入、卖出、或者什么也不做。

而且这个系列能清晰地展示状态怎么压缩。以 121 题为例，用二维 DP 可以开一个n × 2的数组，dp[i][0]表示第 i 天结束时手里没股票的最大现金，dp[i][1]表示第 i 天结束时手里持有一股股票的最大现金。但你很快会发现，第 i 天的状态只依赖前一天，所以完全可以用两个变量来回滚动，把空间复杂度从 O(n) 降到 O(1)。这种“先写出正确但占空间的版本，再优化成滚动数组”的思路，在所有 DP 题目里都有通用价值。

更妙的是，当你掌握了通用状态机，你会发现 309 题、714 题不过是在状态转移方程里加一个时间差或者扣一笔费用。所以这个系列很适合作为“一题一法”到“多题一法”的过渡材料。

2. 暴力枚举：先能跑，再谈优化

很多人，包括我，刚遇到 121 题时第一反应就是两层循环。外层枚举买入的日子，内层枚举卖出的日子，算最大差值。这个思路没错，代码也短，但你可能没认真分析过为什么它慢，以及慢在哪里。

2.1 双层循环的思路与代码实现

假想一个场景：你在水果店买苹果，老板告诉你未来七天的价格，你只能买一次再卖一次。最简单的方法是穷举所有“哪一天买、哪一天卖”的组合。代码如下：

def max_profit_brute_force(prices): n = len(prices) best = 0 for i in range(n): for j in range(i + 1, n): best = max(best, prices[j] - prices[i]) return best

这个代码逻辑上完全正确。如果价格序列是[7, 1, 5, 3, 6, 4]，它能算出最大利润 5（第 2 天买入第 5 天卖出）。但它的内层循环会把每一对买卖组合都算一遍，总共要算 n(n-1)/2 次。当 n 是 10 万时，你需要执行约 50 亿次减法，任何在线评测都无法接受。

这里还有一个容易忽略的细节：题目要求你必须在买入之后卖出，所以内层j必须从i+1开始。有些人想省事直接用j从 0 开始，那就可能出现利润为负数还当作有效答案的情况。

2.2 暴力法的复杂度瓶颈与优化方向

瓶颈在于重复计算。我们在内层循环里，对每个买入日i，都要遍历它后面的所有卖出日。但仔细想一想，对于某个固定的买入日i，真正关心的其实是它后面所有价格中的最大值，只要拿max(prices[i+1:])减去prices[i]就够了。可惜计算每个后缀最大值也需要额外遍历，整体还是 O(n²)。

更优的做法是反过来思考：我不再固定买入日，而是固定卖出日。在第j天卖出时，为了让利润最大，应该在前面的日子里找到价格最低的那一天买入。所以只需要动态维护“截至今天之前的最小价格”，每到一个新价格就尝试用当前价格减历史最低价，更新答案。代码瞬间变成一次循环：

def max_profit(prices): min_price = float('inf') best = 0 for price in prices: min_price = min(min_price, price) best = max(best, price - min_price) return best

这个一次遍历解法的核心其实是贪心。你维护的min_price相当于“历史最佳买入点”，而best始终记录着“如果今天卖出能拿到的最大利润”。这个方法空间 O(1)，时间 O(n)，是 121 题的标准解法。

我建议哪怕你已经会了最优解，也动手写一遍暴力版。因为很多 DP 状态转移方程的推导，本质上就是从暴力解里找重叠子问题。暴力法是帮你理解题意的锚点，不是纯粹的废话。

3. 动态规划状态机：一次交易的标准解法

当题目升级到“最多两笔交易”甚至“最多 K 笔交易”时，一次遍历的贪心就失效了。这时候你需要一种更通用的描述方式，把“第几天”“交易了几次”“是否持有股票”这三个信息组合到一起，这就是状态机 DP。

3.1 状态定义与转移方程推导

以 121 题为例，我从二维 DP 开始讲，方便后面扩展。

定义dp[i][0]表示第 i 天结束时，手里不持有股票时，拥有的最大现金；dp[i][1]表示第 i 天结束时，手里恰好持有一股股票时，拥有的最大现金。初始资金假设为 0，所以不持股时现金为 0，持股时现金相当于花出去了多少钱，是负数。

转移有两种情况：

今天结束时手里没有股票，可能是昨天也没有股票，今天什么都没做；也可能是昨天持有股票，今天把它卖了。所以：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
今天结束时手里有股票，可能是昨天就有股票，今天继续持有；也可能是昨天没有股票，今天刚买入。注意“只能做一笔交易”的限制，这里买入前不能有任何卖出，所以早期买入只能从初始状态转移过来。如果直接用max(dp[i-1][1], dp[i-1][0] - prices[i])，会让“卖出后再买入”成为可能，这在一笔交易条件下是错误的。因此更严谨的写法是把买入特判为-prices[i]，或者引入交易次数维度。

有趣的是，如果题目只要求算一次交易，直接用一维动态规划也能解，即dp[i]表示第 i 天卖出的最大利润，转移是维护前面最小价格。但为了统一后续题型，我推荐直接上手二维状态机。你甚至可以写出伪代码：

def max_profit_dp(prices): n = len(prices) if n == 0: return 0 dp0, dp1 = 0, -prices[0] for i in range(1, n): old_dp0 = dp0 dp0 = max(dp0, dp1 + prices[i]) dp1 = max(dp1, -prices[i]) # 只能买一次，所以用 -prices[i] 而不是 dp0 - prices[i] return dp0

这里有个很关键的细节：买入时用的是-prices[i]，而不是dp0 - prices[i]，就是因为限定了只能做一次交易。如果你的dp0已经包含了一次卖出的利润，那你再用它去买入，那不就是两次交易了吗？所以“一笔交易”和“多笔交易”在状态转移上本质区别就在这一行。

3.2 空间压缩：从二维数组到滚动变量

在上面的代码里，我已经把两个数组压缩成了两个变量dp0和dp1。原因是状态转移只依赖前一天的两个状态，跟更早的日子没有任何关系。这种优化看起来很小，但当你真的去写 188 题的 K 笔交易时，数组空间是n × K × 2，如果 K 也接近 n，内存就可能爆掉。滚动数组可以省下一大块内存。

注意在滚动更新时，dp0的旧值（即昨天的值）会被dp1依赖，所以要么先算dp0再算dp1，要么用一个临时变量把旧值存下来。上面的代码我用old_dp0存了旧值，但其实 121 题里dp1不依赖dp0新值，所以顺序无关紧要。但在多次交易版本里，你必须在更新dp1时使用旧的dp0，这就是很多初学者写出“一天内买又卖”离谱结果的原因。

3.3 通用状态机：不同限制条件统一建模

一旦你接受用“是否持股”作为状态的维度，后续所有题目都可以往这个模型里套。下面我列一个对比表，能一眼看出各题的区别：

题目	核心限制	状态维度	特殊转移
121	最多 1 笔交易	持股/不持股，外加交易次数	买入只能从初始态来
122	不限交易次数	持股/不持股	买入可以从卖出态来
123	最多 2 笔交易	持股/不持股，外加 0/1/2 次交易	需要按次数拆开
188	最多 K 笔交易	持股/不持股，外加 0..K 次交易	三维 DP / 滚动压缩
309	不限次数，卖出后冷冻 1 天	持股/不持股/冷静期	买入需要考虑前两天状态
714	不限次数，每笔扣手续费	持股/不持股	卖出时减去 fee

这张表大约是我刷完整个系列后自己画的。你如果也想高效刷题，建议自己也画一张，并且把每一题的转移方程手写一遍。因为通用建模之后，剩下的全是细节，而细节恰恰是最容易出错的地方。

4. 扩展题型的核心差异与细节解析

系列里的 122、123、188、309、714 看起来都长得很像，但你要是不注意限制条件的字眼，很容易把答案搞错。我按分类把这些差异拆开说。

4.1 多次交易：累加所有上升段

先说 122 题。既然不限交易次数，有人会误以为要模拟所有买卖点，其实根本不用。你可以想象自己在盯盘，只要后一天价格比前一天高，你就能提前在低点买入、高点卖出，然后把这段利润装进口袋。当然，现实里你不能无限买卖，但题目允许的话，这个操作就是最优的。

所以 122 题最简解法是：

def max_profit(prices): profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] return profit

这个解法有点“开后门”的感觉，但它是严格正确的。因为它把每一段上涨都拆分成了相邻两天的差值，数学上等于每天做一次即时卖出并重新买入。用状态机 DP 也能得到同样的答案，而且状态转移更显式：

def max_profit_dp(prices): n = len(prices) if n == 0: return 0 dp0, dp1 = 0, -prices[0] for i in range(1, n): old_dp0 = dp0 dp0 = max(dp0, dp1 + prices[i]) dp1 = max(dp1, old_dp0 - prices[i]) return dp0

注意这里dp1用的是old_dp0 - prices[i]，意思是“前一天不持股时（可能已经赚了几笔）的现金用来买入新股”，所以可以无限次交易。这个差别正是 121 和 122 的命门。

4.2 含手续费与冷冻期：状态机加约束

714 题与 122 题唯一的区别是每笔交易要扣手续费。手续费可以当作卖出时额外减去一笔钱，也可以在买入时减去。常见写法是卖出时减去fee：

dp0 = max(dp0, dp1 + prices[i] - fee)

需要注意，如果使用dp1 + prices[i] - fee，那么卖出后现金会变少。这是合理的。可有些人会搞混手续费是一次性还是每笔都扣，其实题目已经说清楚“每笔交易都要收手续费”，一买一卖算一笔，所以只在卖出时扣一次就够了。

309 题的冷冻期则更有意思。它要求卖出股票的下一天不能买入。这意味着当你今天想买入时，必须确认昨天没有卖出过。于是状态机需要多一个维度：冷冻状态。你可以定义三个状态：hold（持有）、sold（卖出当天）、rest（冷静期）。其实更简单的办法是：在计算买入时，跳过前一天的卖出状态。

我给你一个比较直接的三状态 DP：

def max_profit(prices): n = len(prices) if n == 0: return 0 rest, hold, sold = 0, -prices[0], 0 for i in range(1, n): pre_rest = rest pre_hold = hold pre_sold = sold rest = max(pre_rest, pre_sold) # 今天不操作，且不在冷冻期 hold = max(pre_hold, pre_rest - prices[i]) # 只有休息状态才能买入 sold = pre_hold + prices[i] # 只有持有才能卖出，卖出后进入冷冻期 return max(rest, sold)

这里的核心是hold只能从rest转移，因为卖出后的第二天必须冷静，不能买入。我建议你把三个变量用纸笔推一轮，比如用价格序列[1,2,3,0,2]，算完后利润应该是 3。推过一次，你就明白为什么要用pre_rest而不用更新后的rest。

4.3 K笔交易：三维DP与边界处理

123 和 188 题把次数约束变成数字。以 123 题为例，最多两笔交易。暴力做法是枚举第一笔卖出日和第二笔买入日，但那样会 O(n²)。状态机做法是给 DP 增加交易次数维度：dp[i][k][0/1]表示第 i 天，已经完成了 k 笔交易，当前是否持股。

这里有个容易混淆的点：到底在买入时计数，还是卖出时计数？两种约定都行，但必须保持一致。我习惯在买入时计数，这样卖出时就不再加次数。状态转移如下：

不持股状态：dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k-1][1] + prices[i])（注意这里的第二项表示在第 i 天卖出，完成了一笔交易，所以 k-1 到 k）
持股状态：dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])

你会发现写出来其实特别规整。但初始化容易翻车：dp[0][0][1]应该在第一天就持股，现金为-prices[0]；而dp[0][k][1]对 k>0 应该设为负无穷，表示不可能。

代码示意如下：

def max_profit_k(K, prices): n = len(prices) if n == 0 or K == 0: return 0 # 初始化两个状态数组，分别表示不持股和持股 dp0 = [0] * (K + 1) dp1 = [-float('inf')] * (K + 1) for price in prices: for k in range(1, K + 1): # 先算不持股 dp0[k] = max(dp0[k], dp1[k] + price) # 再算持股，买入算一次交易，这里用 dp0[k-1] dp1[k] = max(dp1[k], dp0[k-1] - price) return dp0[K]

注意这里dp0表示不持股但已经完成了k笔交易，dp1表示持股且已经完成了k笔交易（买入时已计数）。每一轮价格都要更新所有 k，而且必须从 1 到 K 正向遍历，因为dp0[k-1]是这一天的值还是上一天的值？在滚动数组里，我们需要保证dp0[k-1]是上一天的值，所以应该逆序遍历 k，否则同一个价格会重复买入。正确做法是：

for price in prices: for k in range(K, 0, -1): dp0[k] = max(dp0[k], dp1[k] + price) dp1[k] = max(dp1[k], dp0[k-1] - price)

逆序的原因是，dp0[k-1]在更新后可能已经包含了今天的操作，如果正序遍历，你再拿它去买，就相当于在一天内完成了一次卖出和一次买入，这在逻辑上会产生一次不存在的交易。这个坑我在实际写 188 题时踩过，调试了很久才想起来滚动数组的方向问题。

5. 常见问题与排查技巧实录

刷这一系列题的时候，我遇到过一些挺典型的困惑，这里挑几个有代表性的说说。

5.1 晦涩的状态转移，到底怎么理解

很多人看到dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])会问：为什么dp[i-1][1]加上今天的价格就是卖掉后的现金？你要把dp[i-1][1]当成“昨天结束时持有的股票所对应的现金价值”，它本身是个负数或者一个相对值。比如昨天持股花了 1 元买，今天价格 5 元，那么dp[i-1][1] + prices[i]就相当于把昨天那 1 元成本收回来，再赚 4 元。所以这个式子里的dp[i-1][1]并不是可支配现金，而是持股状态下折算的净值。理解到这一层，你就能看懂所有状态机转移。

我发现最有效的理解方式是“把每一笔交易看成一次现金流的进和出”。买入就是现金流出，卖出就是现金流入。DP 记录的是“当前手里的现金净值”，而不是累计利润。初始现金是 0，买入后现金是-prices[i]，卖出后现金增加。这样每个状态都是一个账户余额，转移方程自然就写出来了。

5.2 边界条件与初始化踩坑记录

边界条件往往是这类题的大坑。第一，数组为空或只有一个元素时，最大利润一定是 0，因为根本做不了买卖。第二，如果 K 大于天数的一半，实际上相当于不限交易次数，因为买卖需要两个不同的日期，最多也就 n/2 笔。有些题还会给你一个很大的 K 值，如果你硬开n × K的数组，内存直接爆掉，这时候要先做K = min(K, n // 2)的剪枝。第三，初始化时，任何“不可能达到”的状态应该用负无穷而不是 0。比如在第 0 天就完成了 1 笔交易且持股，这是不可能的，如果初始化为 0，后面的转移会算出“凭空买入”的利润，结果就错了。

我建议刷题前先把所有状态数组打印出来，看几个关键日期：第 0 天、第 1 天、最后一个交易日。手动模拟一遍 121 题的二维 DP，你就知道为什么要给dp[0][1]赋值-prices[0]，而不是 0。往往一个小初始化错误，就能让整个动态规划逻辑变得貌似合理但答案错误。