C++状态机DP通解LeetCode买卖股票六连题

“买卖股票的最佳时机”这组题，可能是 LeetCode 上最容易被低估的系列。121 到 188，加上 714，一共六道，表面看全是“给定股价数组求最大收益”，但限制条件从“最多交易 1 次”一路叠加到“最多 k 次、冷冻期、手续费”，难度直接从简单冲到困难。我当年刷题是挨个题号硬啃的，每道都重新想一遍，直到去面试被追问“这几道题之间到底什么关系”才真正意识到，它们就是同一个二维状态机的六个参数化变体。这篇文章就用 C++ 把这六道题全部拆开讲清楚，从最朴素的写法到空间压缩版本，顺带把我在机考和笔试里踩过的整型溢出、初始化顺序、边界条件这些坑全部说透。适合正在备校招机考、准备 GESP/CSP 认证，或者刚学完 C++ STL 想找一组经典动态规划题练手的朋友。

1. 先看清这组题到底在考什么

1.1 六道题的家谱与难度阶梯

先给一张总表，把六道题摆在一起看，比一道一道刷要清楚得多：

这张表的信息量其实很大。你看 123 和 188，一个是“最多两笔”，一个是“最多 k 笔”，k 取 2 的时候就是 123；188 的 k 取 1 就是 121。所以 188 本质上是 121 和 123 的通用版本。至于 122，它是 k 趋向正无穷的极限情况，这也是为什么很多贪心解法只对 122 成立，因为一旦交易次数有限，你就不能“见涨就卖”，必须考虑把交易额度留给后面更大的涨幅。

我个人的建议是：121、123、188 必须按顺序刷，这三道是一根主线；122、309、714 是三个独立变体，分别考验“贪心边界”“状态拆分”“参数偏移”三种能力。主线吃透了，变体就是加一行条件的事。

1.2 为什么状态机比公式推导更抗打

很多教程讲 121 只讲一句话：记录历史最低价，每天算一下卖出利润。这确实是最优解，但如果你只记住了这个公式，到了 123 就会彻底懵掉，因为有两笔交易时，第一笔的“卖点”会直接影响第二笔的“买点”，单靠一个最低价变量根本表达不了这种耦合关系。

所以要切换到状态机的思维：我不去推导“哪天买、哪天卖”的公式，而是只盯住每天结束时“我手里处于什么状态”。状态之间可以互相转移，每一种转移对应一笔现实操作。这个想法的优势是扩展性极强——你后面加的每一个限制条件，本质上就是在状态定义或者转移方程里加一个约束，而模板本身纹丝不动。我刷完这一组题后最大的体会是：动态规划题如果第一反应是“设 f(i) 表示第 i 天怎么怎么样”，大概率会越推越乱；但如果第一反应是“第 i 天有哪些状态，状态之间怎么转移”，哪怕推不出来，也至少能把 O(n²) 的暴力 DP 写对，这在机考里已经能拿到大量分数了。

1.3 你需要哪些 C++ 基础

说句实话，这组题对 C++ 语法本身的要求非常低，核心就三样：vector<int>的创建和遍历、std::max/std::min、INT_MAX/INT_MIN这种极限值常量。连排序、哈希表、二分查找都用不上，所以它特别适合用来验证自己“入门了没”——语法都会，但 DP 不会，刷完这组就相当于把动态规划的基本功补上了。

我用到的代码风格是在竞赛和机考题里最常见的写法：for (int price : prices)范围遍历，max(hold + price, cash)这种一行更新。如果你用的是老编译器，注意bits/stdc++.h万能头依赖环境，老老实实写#include <vector>+#include <algorithm>在任何环境下都不会出错。

2. 状态机模型：一套模板通吃所有变种

2.1 状态定义：用“现金”而不要用“利润”

很多初学者上来就定义dp[i]表示前 i 天能赚的最大利润，然后就开始纠结“我今天卖了，那昨天是不是必须持股”“持股的成本价要不要带进转移”之类的问题，越绕越晕。我试过好几次，最顺手的定义是把“持有的现金”当作状态值，而不是“利润”。

• dp[i][0]：第 i 天结束时，手上没有任何股票，账户里有多少现金。
• dp[i][1]：第 i 天结束时，手上持有 1 股股票，账户里有多少现金。

注意第 2 个状态下现金可能是负数，因为买股票是“先垫付”的。你可以把初始现金看成 0，买入花掉prices[i]，现金变成-prices[i]；卖出时收回来，现金加上prices[i]。一开始把数组初始化为 0 也不会影响正确性，因为所有现金值都是相对位移，最后结果都是最大值。

这个定义的妙处在于：你不用记“我怎么买、怎么卖”，只需要问一个问题——今天结束的时候，我手里有没有股票？剩下的全部由转移方程回答。

2.2 两个转移方程是怎么推出来的

第 i 天结束时不持股，只有两种可能：要么第 i-1 天就不持股，今天什么也没干；要么第 i-1 天持股，今天把股票卖了。所以：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])

第 i 天结束时持股，也只有两种可能：要么第 i-1 天就持股，今天继续拿着；要么第 i-1 天不持股，今天买入。所以：

dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

这就是全部家底。用生活化一点的话说：你今天要么“保持原状”，要么“做一笔操作”，取两种选择里现金更多的那个。

初始值也很直白：dp[0][0] = 0，dp[0][1] = -prices[0]，意思是第一天要么空仓，要么花掉第一天的价格买入。后面的每一天都套这两个方程，最后答案一定是dp[n-1][0]，因为手里拿着股票不清仓，永远不能说收益落袋了。

2.3 当交易次数也变成维度：三维状态模型

到了 123 和 188，光靠“持不持股”两个状态不够了，因为“这是第几笔交易”会直接影响“我还剩几次买入机会”。所以状态变成三维：

• dp[i][j][0]：第 i 天结束时，已经完成 j 笔交易，手里不持股。
• dp[i][j][1]：第 i 天结束时，已经进行了 j 笔交易（买入过 j 次），手里持股。

这里有个特别容易出错的约定：我选择在“买入”时把交易次数加 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])

第一个方程照旧，卖出不消耗交易次数，因为买入时已经记过一次了；第二个方程里，买入一笔新的，需要从“已经完成 j-1 笔但不持股”的状态转移过来。记住：交易次数是“买”出来的，不是“卖”出来的，这样整个系列只有一处要注意次数变化，其他的全是复制粘贴。

3. C++ 逐题拆解：从 121 到 714

3.1 121：最简版本，扫描和 DP 都能过

121 是“最多一笔交易”，所以最简单粗暴的解法是记录历史最低价，然后每天算“今天卖能赚多少”：

int maxProfit(vector<int>& prices) { int minPrice = INT_MAX; int ans = 0; for (int price : prices) { ans = max(ans, price - minPrice); minPrice = min(minPrice, price); } return ans; }

这个解法的时间是 O(n)，空间 O(1)，而且好写。但它并不容易扩展，因为“最低价”的概念只适用于“只能买一次”。为了和后面的 DP 统一，我建议你也把 DP 写法写一遍：

int maxProfit(vector<int>& prices) { int n = prices.size(); if (n < 2) return 0; int cash = 0; int hold = -prices[0]; for (int i = 1; i < n; ++i) { cash = max(cash, hold + prices[i]); hold = max(hold, -prices[i]); // 只允许一次买入，买过就锁死 } return cash; }

注意这一行hold = max(hold, -prices[i])，它和 122 的区别是致命的：这里买入永远是从“初始现金 0”出发，而不是从“上一轮卖出后的现金”出发。也就是说，哪怕你之前卖出赚了钱，也不允许用这笔钱再买第二回。这就是 121 的正确约束：最多一笔，卖完就收工。这个细节不看代码很难体会，我当初就是在这个“-prices[i]”和“cash - prices[i]”之间迷了很久。

3.2 122：贪心能过，但 DP 才是主线

122 不限交易次数，所以有个著名的贪心：只要今天的价格比昨天高，就把这个差价赚到。写成代码就是：

int maxProfit(vector<int>& prices) { int ans = 0; for (int i = 1; i < prices.size(); ++i) if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1]; return ans; }

这个贪心为什么对？因为不限次数，所以任何一段上升趋势都可以拆成若干“今天买明天卖”的片段，累加所有正差价就是全局最优。但你要明白，这个结论是“次数无限”这个前提给的。一旦把“最多 k 次”加回来，贪心就直接失效。

所以我更推荐把 DP 写法当成主线，因为它和 121 只有一行之差：

int maxProfit(vector<int>& prices) { int n = prices.size(); if (n < 2) return 0; int cash = 0; int hold = -prices[0]; for (int i = 1; i < n; ++i) { int preCash = cash; int preHold = hold; cash = max(preCash, preHold + prices[i]); hold = max(preHold, preCash - prices[i]); } return cash; }

对比 121，这里唯一的变化就是买入时要写成preCash - prices[i]，意思是你可以用之前卖出赚到的现金继续买。这两个版本的差异，就是整组题最重要的分水岭：限制次数时，买入来自初始本金；不限次数时，买入来自已实现利润。你把这一个点记住，后面所有题都只是在这个结构上做加减法。

3.3 123：最多两笔，四个变量滚动更新

123 是 188 取 k=2 的特例，但因为它只有两笔，可以不写二维数组，直接用四个变量滚动：

int maxProfit(vector<int>& prices) { int buy1 = -1e9, sell1 = 0; int buy2 = -1e9, sell2 = 0; for (int price : prices) { buy1 = max(buy1, -price); sell1 = max(sell1, buy1 + price); buy2 = max(buy2, sell1 - price); sell2 = max(sell2, buy2 + price); } return sell2; }

这四个变量的含义分别是：第一次买入后现金、第一次卖出后现金、第二次买入后现金、第二次卖出后现金。为什么要按 buy1 -> sell1 -> buy2 -> sell2 的顺序更新？因为 sell1 依赖本天的 buy1，buy2 依赖本天的 sell1——顺序写反了就会用到昨天的旧值，结果就错了。不过这里的“本天先卖后买”其实是被允许的：你在同一天卖掉第一笔，立刻用这笔钱买第二笔，相当于两笔交易在同一天完成，但等价于一次持股时间更长的交易，并不会让答案变大，所以这样写是安全的。

我拿一个经典样例验证过：prices = [3,3,5,0,0,3,1,4]，答案是 6，即 0 元买 3 元卖，再 1 元买 4 元卖。你可以在草稿纸上手动跟踪这四个变量跑一遍，会非常直观地看到第一笔的收益“喂”给第二笔的买入价。

3.4 188：完整的三维 DP 终于出场

188 是整组题的正主，代码值得逐行吃透：

int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if (n < 2 || k == 0) return 0; // 每笔交易至少需要一买一卖两天，k 超过 n/2 时限制等于没有限制 if (k >= n / 2) { int ans = 0; for (int i = 1; i < n; ++i) if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1]; return ans; } // dp[j][0]：完成 j 次交易后不持股；dp[j][1]：完成 j 次交易后持股 vector<vector<int>> dp(k + 1, vector<int>(2, -1e9)); dp[0][0] = 0; for (int price : prices) { for (int j = k; j >= 1; --j) { dp[j][0] = max(dp[j][0], dp[j][1] + price); dp[j][1] = max(dp[j][1], dp[j - 1][0] - price); } } return dp[k][0]; }

这里有三个关键点，缺一个都会出问题。

第一个是k >= n / 2的退化处理。一次完整的交易至少占用两天，所以最多只能做n/2笔交易；如果 k 比这个还大，说明限制额度根本用不完，问题退化成 122 的不限次数，直接用贪心 O(n) 扫一遍。这个优化不只是省时间，更重要的是防止后面建一个k x 2的大数组去跑一个无意义的循环——k 可能到 10^9，直接建数组会爆内存。

第二个是内层循环必须倒着写for (int j = k; j >= 1; --j)。因为dp[j][1]的更新要用dp[j-1][0]，如果 j 从小到大，dp[j-1][0]已经被这一轮更新成“今天买入后的状态”了，那dp[j][1]就等于允许“今天买完马上再买”，语义就乱了。倒着遍历能保证dp[j-1][0]还是昨天结束时的旧值，这就是滚动数组的经典手法。

第三个是初始化别用INT_MIN，用-1e9。原因我在下面第 4 节专门展开，这里先记住一句话：INT_MIN + price在 C++ 里是未定义行为，轻则答案错，重则机考现场崩溃。

3.5 309：冷冻期逼出一个“第三状态”

冷冻期的规则是：卖出股票的第二天不能买。这时候“不持股”的状态要拆成两个——是“普通空仓可以买”，还是“今天刚卖不能买”。我用的三状态写法是：

int maxProfit(vector<int>& prices) { int n = prices.size(); if (n < 2) return 0; int rest = 0; // 空仓且不在冷冻期 int hold = -prices[0]; // 持股 int sold = 0; // 今天刚卖出，明天不能买 for (int i = 1; i < n; ++i) { int preRest = rest; int preHold = hold; int preSold = sold; rest = max(preRest, preSold); hold = max(preHold, preRest - prices[i]); sold = preHold + prices[i]; } return max(rest, sold); }

转移逻辑拆开看就三条：rest可以由昨天的rest（继续空仓）或昨天的sold（冷冻期结束）得到；hold可以由昨天的hold（继续持有）或昨天的rest（普通空仓时买入）得到；sold只有一个来源，就是昨天持股今天卖掉。注意rest - prices[i]用的必须是preRest，绝不能是更新后的rest，否则就会从“明天才解冻”的状态里买股票，直接破坏冷冻期约束。

我拿[1,2,3,0,2]手算过一遍：最优策略是 1 买 3 卖，然后 0 买 2 卖，总利润 4。哦，等一下，我记得答案是 3，因为 1 买 3 卖赚 2，0 买 2 卖赚 2，总利润应该是 4？你再仔细看这道题原题，经典的[1,2,3,0,2]答案是 3。为什么？因为第一个操作如果是 1 买 3 卖，卖掉后的第二天是冷冻期，你没法在 0 那天买，只能在之后买，所以最优其实是 1 买 2 卖（赚 1）→ 冷冻期跳过 3 → 0 买 2 卖（赚 2），一共 3。这种“看上去更美但被冷冻期挡住”的案例，只有状态机才讲得清楚，用公式推很容易漏。

3.6 714：手续费只是一个常数偏移

714 是所有题里最温柔的，它只要求你在计算收益时扣掉一笔固定的手续费。我习惯在买入时扣费，这样卖出时不用再管任何手续费的事：

int maxProfit(vector<int>& prices, int fee) { int n = prices.size(); if (n < 2) return 0; int cash = 0; int hold = -prices[0] - fee; for (int i = 1; i < n; ++i) { int preCash = cash; int preHold = hold; cash = max(preCash, preHold + prices[i]); hold = max(preHold, preCash - prices[i] - fee); } return cash; }

比如prices = [1,3,2,8,4,9], fee = 2，最优是 1 买 8 卖（扣 2 手续费，净赚 5），4 买 9 卖（净赚 3），合计 8。你按这个代码手推一遍，会发现每笔买入现金都会先扣掉 fee，卖出时全额回收，这样手续费就精确地只扣一次，不会出现买卖两边都扣或都不扣的偏差。

这里有个小陷阱值得说：如果你习惯在“卖出”时扣费，也是对的，但一定不能两边都扣，否则结果偏小。选哪边只影响hold的初始值，不影响最终答案。我个人的习惯是统一买入扣费，因为这样hold的初始值很直观：第一天买入，付出prices[0] + fee。

4. 高频踩坑与调试实录

4.1 边界条件：空数组和 k=0 永远最先检查

我见过太多人在机考里栽在这个地方。prices.size() < 2时，一天连买带卖都凑不齐，直接返回 0；k == 0时，不允许任何交易，也是 0。这两条建议写进每道题的第一行。还有一个隐蔽的边界：n == 2且价格递减，比如[3, 2]，正确答案是 0（不交易），不要被“2 买 3 卖”这种幻觉迷惑，因为根本不存在 2 在后的历史最低价。

4.2 整型溢出：INT_MIN 加上正数直接 UB

这是 C++ 特有的坑，也是我最想说的一段。在 188 的代码里，如果你写vector<vector<int>> dp(k + 1, vector<int>(2, INT_MIN))，那么第一天执行dp[j][0] = max(dp[j][0], dp[j][1] + price)时，INT_MIN + price是一个溢出的未定义行为。理论上编译器和 OJ 环境想怎么处理就怎么处理，有的环境恰好算出一个极小数然后被 max 丢掉，看起来“没问题”，但换一个环境就可能在调试器里爆出各种诡异结果。

解决办法有三个，我按推荐顺序排：第一，用-1e9这种“足够负但不是极限值”的哨兵，因为 LeetCode 的价格上限通常是 10^9 级别，-1e9减去一个价格也不会下溢，而INT_MIN减价格一定会下溢；第二，直接开long long，用-4e18当哨兵，反正机考不会因为你用 64 位整数扣分；第三，把第一天单独初始化掉，不让INT_MIN参与运算。我在实际答题时最常用第一种，因为它不用改类型，代码看起来也更干净。

4.3 滚动数组最常见的顺序错乱

用两个变量滚动更新时，最大的敌人是“新值覆盖旧值”。比如 122 的写法，如果写成：

cash = max(cash, hold + price); hold = max(hold, cash - price); // 这里用了今天的 cash，错了

那hold的买入就使用了今天刚刚卖出的现金，等于当天先卖后买。这个行为在 122 里居然经常是对的，因为当天先卖后买等价于不操作，不会让答案变大；但在 309 里就彻底错了，因为当天卖出后会触发冷冻期，当天再买违反规则。所以我的纪律是：凡是滚动数组，先把昨天的值快照出来，再统一更新，名字就叫preCash、preHold，一眼就能看出“我用的全是昨天的东西”。这个习惯帮我避免了很多难以察觉的 off-by-one 错误。

4.4 调试三板斧：小样例、打印 dp、对拍

动态规划写错了，看代码通常是看不出来的，因为错在“状态没转移对”，而不是语法问题。我调试这组题的标准流程是三步。

第一步，找一组 4 到 5 天的微型样例，比如[1,2,3,0,2]，答案背得出来，方便手算。第二步，在关键循环里打印 dp 表，看每个交易次数下cash和hold的演变过程有没有违背直觉的地方。第三步，如果实在找不出错，就把 188 的 k 分别设成 1、2、n/2，和 121、123、122 的答案对一下，理论上必须完全一致，对不上就说明三维 DP 的交易次数计数有问题。

我也分享一个实用的打印小工具，就是在一个样例上把每一天的dp打出来：

for (int j = 0; j <= k; ++j) printf("j=%d cash=%d hold=%d\n", j, dp[j][0], dp[j][1]);

打印一次你就会发现，很多“我以为的状态”和“实际的状态”根本不是一回事。比如dp[0][1]永远不该被更新（你没有交易过却持有股票，这是不可能状态），如果打印出来发现它变了，那一定是买入时的维度写错了。

5. 复杂度总表与面试实战

5.1 六道题的复杂度总表

把这组题刷完，复杂度应该烂熟于心：

面试时被问“能不能再优化”，你要能立刻答出：188 的时间复杂度 O(nk) 已经是下限，因为要遍历每个价格和每个交易次数；空间从 O(nk) 优化到 O(k) 是靠滚动数组，原理是第 i 天的状态只依赖第 i-1 天。这组题如果被问到“内存不够怎么办”，还有一招是把 k 和 n/2 取 min，因为 k 再大也不会超过 n/2，这一步既省时间又省空间，面试官吃这一套。

5.2 面试官最爱追问的三个点

第一个是“188 里为什么 k >= n/2 就能退化成不限次数”。答案是一笔交易至少要占用“买入、卖出”两个不同的日子，n 天最多完成 n/2 笔完整交易，所以 k 超过 n/2 就意味着额度永远用不完，和无限次没有区别。

第二个是“三维 DP 能不能压成二维”。能，但前提是你得理解，dp[i][j][0/1]的 i 维可以被滚动掉，因为第 i 天的状态只依赖第 i-1 天，并且我们在内层倒序处理 j，保证每次用的都是“昨天的 j 或 j-1”，而不是“今天的”。很多候选者能背出代码，但解释不清倒序的原因，你如果能讲透这一点，面试印象分会高很多。

第三个是“如果要求输出具体哪天买哪天卖怎么办”。这就要从 DP 回溯了：从dp[n-1][k][0]往回走，如果dp[i][j][0] == dp[i-1][j][1] + prices[i]，说明第 i 天卖出了，再往前找对应买入日。这个扩展题我在面试里被问过两次，第一反应千万不要慌，它考的就是你对状态转移方程的熟悉程度。

5.3 给备考机考和面试的几条实在建议

这组题在 GESP、CSP 这类认证的机考里也是常客，我根据自己刷题和带人备赛的体会说几条：

第一，别只刷 121 就往下走。很多人被“简单题”给骗了，觉得股票题不过如此，结果到了 188 直接卡住。我的建议是要么不碰这组，要碰就六道连刷，而且每道都从“统一模板”的角度去写，不要每道题各自发明写法。

第二，手写代码比看代码重要。尤其是 188，闭卷在纸上写一遍，能写对，才说明你真的理解了维度、倒序和哨兵值这三件事。等到机考时，你根本不需要思考，手指会自动把模板打出来，这种“肌肉记忆”在时间紧张的时候最救命。

第三，边界测试不要省。每次写完，至少跑四个用例：空数组、单元素数组、严格递增数组、严格递减数组。前两个验证空输入保护，后两个验证答案是否真的是 0 或最大差价，能立刻暴露很多隐性问题。

第四，如果题目没有明确说数据范围，我建议直接全部门函数用int，内部状态值用long long兜底。这不是过度设计，而是我确实见过有人因为prices[i]上限 10^9、n 上限 10^5 时，用 int 存总利润导致溢出，答案差一位数，怎么调试都找不到原因——最后发现是类型问题。

最后分享一个小技巧：这组题的六道代码，核心差异其实只有一个“买入时能不能用已实现利润”。你把 121 的-prices[i]改成cash - prices[i]就得到 122；把 122 加上第二维交易次数就得到 188；在 188 的买入前强制空仓一天就得到 309；在 188 的买入时减掉 fee 就得到 714。用这个视角去复习，六道题就等于一道题，考场上看到任何变体，心里都有底。