从LeetCode那个经典的股票系列开始说。股票买卖问题，应该是很多C++初学者第一次直观感受到"同一个场景，两种截然不同的解法"的入口。场景一句话就能说清：给你一个数组prices，prices[i]表示第 i 天的股票价格，问怎么买卖能获得最大利润。听起来像炒股指南，实际上跟真实交易没太大关系，它就是一个把"选择"建模成最优化问题的算法题，核心考察你对贪心算法和动态规划这两套思路的理解深度。这篇文章我想从C++实现的角度，把整条脉络完整串一遍：遇到股票题先想什么，贪心怎么落地，DP状态怎么设计，变体怎么推，以及我实际跑代码时踩过的那些初始化、边界和溢出坑。适合刚学完C++基本语法、准备系统刷题的朋友，也适合面试前想快速把这类题目过一遍的同行，读完你至少能独立把 LeetCode 121、122、714、309 这几道"同场景不同限制"的题写出来，并且知道为什么有的题只能上 DP，有的题贪心就够了。
1. 先把问题看穿：股票系列到底在考什么
1.1 一次买卖的数学本质：最大化一个差值
很多新手一上来就被"股票""买卖"这些词带偏，觉得要研究均线、K线、成交量，其实完全不用。算法题里的股票买卖就是一个纯数学问题：选择一个买入日 i，再选择一个买入日之后的卖出日 j，目标是最大化prices[j] - prices[i]。就这么简单。
如果只允许一次交易，最笨的写法是双重循环枚举所有(i, j)组合，找出差值最大的一组。代码写出来确实能过样例，但一旦n到 10 万级别，O(n²) 的复杂度就彻底崩了。我之前拿[7,1,5,3,6,4]这个官方样例跟朋友演示，问能不能一眼看出答案是 5（第 2 天买、第 5 天卖），然后再问"如果给你 10 万天的价格，你还能一眼看出来吗"，大多数人这时候才意识到，算法优化的核心是把"全量比较"压缩成"遍历一次就出结果"。
这里有个很重要的思维习惯：做题前先把题目翻译成自己能懂的数学模型。股票题翻译过来就是"给定一个序列，找两个位置使得差值最大"，而不同变体只是在"找两个位置"之前加了一堆买卖次数、手续费、冷冻期之类的限制条件。你想清楚了这一点，就不会被题目表面的商业词汇干扰。
1.2 变体地图：为什么同一场景能出六道题
LeetCode 上股票问题是一个完整系列，难度和限制条件递增：
| 题号 | 限制条件 | 核心考点 |
|---|---|---|
| 121 | 只能买卖一次 | 最小值追踪 / 简单DP |
| 122 | 可无限次买卖 | 贪心累计上涨段 |
| 123 | 最多买卖两次 | 三维DP状态 |
| 188 | 最多买卖 K 次 | 状态维度 +1 |
| 309 | 卖出后有一天空仓期（冷冻期） | 三状态状态机 |
| 714 | 每次交易收手续费 | 成本入方程 |
这个表格是我每次给新手讲股票题必画的东西。原因很朴素：你刷题如果只刷一道 121，可能觉得这题水得很；但如果把六道连在一起看，你会发现它们其实是同一棵树上长出来的六个分支，区别只在于"限制条件"，而这些限制条件会直接影响状态设计。
理解这一点有个额外的好处：你不会再觉得"动态规划好难、我看不懂"——因为当你能把六道题的状态定义和转移方程整齐地列出来时，它们就不再是六道孤立的题，而是一套可以互相印证的体系。
1.3 两种算法思维的分水岭：贪心和 DP 各管哪一段
简单说，贪心算法强调的是"每一步都做当前看起来最优的选择"，它假设局部最优能累积成全局最优；动态规划则强调"枚举所有可能状态，通过状态转移吸收历史信息"，它不依赖局部最优假设，只依赖状态定义的完备性。
股票题目里，这两者的分界线非常清晰。无限次交易、没有手续费、没有冷冻期时，贪心成立；一旦加入"交易次数上限""手续费""冷冻期"这类限制，贪心的局部最优假设就会被打破。所以面试时如果让我选解法，我会先看限制条件，再决定上贪心还是 DP。
2. 贪心算法：先把最简单的解写出来
2.1 只买卖一次：用两个变量完成线性扫描
121 题的最佳解法其实叫"最小值追踪法"，思路非常直观。我遍历价格数组时维护两个变量：
minPrice：到目前为止出现过的最低价格；maxProfit：到当前天为止，如果卖出能得到的最大利润。
每天的行情来了之后，先更新minPrice（因为日子越靠后的"低点"越可能是未来的买入点），然后计算"如果今天卖出，能赚多少"，再更新maxProfit。这段代码极其精简：
class Solution { public: int maxProfit(vector<int>& prices) { int minPrice = INT_MAX; int maxProfit = 0; for (int price : prices) { minPrice = std::min(minPrice, price); maxProfit = std::max(maxProfit, price - minPrice); } return maxProfit; } };这里有个容易被新手忽略的点：为什么minPrice初始值要设成INT_MAX，而不是prices[0]？因为如果数组为空，你直接取prices[0]会越界崩溃；用INT_MAX配合std::min，第一次循环时自然会被第一个价格覆盖，同时空数组场景也能安全返回 0。
为什么这个贪心是对的？因为"一次买卖"的最优买入点，必然是某个历史最低点；最优卖出点必然是某个历史最高点（在买入点之后）。你维护的minPrice其实相当于"到目前为止的最优买入候选"，而price - minPrice就是"当天卖出候选"。全局最优一定是某个"历史最低点 + 之后的最高点"，所以扫描一遍就能保证不漏掉最优解。
2.2 无限次交易：把单调上涨段全部吃掉
122 题换了个条件：可以买卖无数次，但每次只能持有一股。这题的贪心策略是：只要今天的价格比昨天高，就认为"昨天买入、今天卖出"是值得做的，把差价累加进利润。代码更短：
class Solution { public: int maxProfit(vector<int>& prices) { int profit = 0; for (int i = 1; i < prices.size(); ++i) { if (prices[i] > prices[i - 1]) { profit += prices[i] - prices[i - 1]; } } return profit; } };为什么累加所有正差价就能得到最大利润？你可以把一个完整的上涨区间拆开，比如价格从 1 涨到 5，中间经过 2、3、4，那么"第 1 天买、第 5 天卖"赚 4，"每天低买高卖"累计是 1+1+1+1=4，结果完全一样。
这个结论背后是无限次交易 + 无手续费这两个前提：交易次数不花钱，所以交易得越频繁越好；而所有正差价之和，恰好等于把所有上涨波段的涨幅全部收入囊中。反过来，如果遇到下跌段，你只要不持有就行，不需要做任何操作。
写这段代码时我踩过一个脑残坑：if (prices[i] > prices[i-1])我一开始写成了>=，结果遇到连续两天价格相同的情况也累加差价，利润凭空多出 0。虽然结果不影响（0 加不加都一样），但逻辑上不干净，面试时被追问会显得不够严谨。
2.3 贪心的边界：什么时候"有涨就吃"会失效
你必须清楚地知道贪心解法的适用边界。最简单的一个反例是加手续费的情况：假设每天价格是[1, 2, 3]，每次交易手续费 2 元。用贪心的思路，第 1 天买第 2 天卖赚2-1=1，扣掉手续费 2 反而亏 1；第 2 天买第 3 天卖又是亏 1。但如果全程不交易，利润是 0。也就是说，高频交易在这种情况下是负收益，贪心策略直接失效。
这个例子告诉我们：贪心算法本质是在"当前局部"做判断，它看不到"这次交易的收益能不能覆盖成本"这种全局信息。只要限制条件多起来，比如手续费、冷冻期、交易次数上限，贪心的"局部最优加起来等于全局最优"这个前提就不成立了。这时候你需要的是一个能够穷举所有状态、在状态之间做最优转移的框架——这就是动态规划登场的时候。
3. 动态规划：用状态机统一所有股票题
3.1 为什么要引入"状态"
从 121、122 到 714、309，命题人只是往场景里塞了几个限制条件，解法就从"扫描变量"升级成"二维DP"甚至"三维DP"。根本原因在于：当你引入交易次数、手续费、冷冻期之后，任意一天的收益不仅取决于当天的价格，还取决于"你现在手里有没有股票""这是第几次交易""是不是刚卖出处于冷静期"这些历史状态。
动态规划的思路是把这些历史状态显式建模。设计状态的基本原则是"不重不漏"：每个状态能完整描述某个时刻的所有关键信息，并且状态之间的转移能覆盖所有可能的变化路径。对应股票问题，最常见的状态集合就是"当天结束时手里是否持有股票"。
3.2 C++实现的基础 DP 版和滚动数组版
直接给代码。这里我用两个维度：dp[i][0]表示第 i 天交易结束、手里不持有股票时的最大利润；dp[i][1]表示第 i 天交易结束、手里持有一股时的最大利润（持有股票时利润为负数，因为它占用了现金）。
转移方程是两个max：
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])
含义分别是：今天不持有，要么昨天就不持有继续观望，要么昨天持有今天卖出；今天持有，要么昨天就持有继续拿，要么昨天不持有今天买入。
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if (n < 2) return 0; vector<vector<int>> dp(n, vector<int>(2, 0)); dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < n; ++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]); } return dp[n-1][0]; } };如果你面试时觉得二维数组占空间浪费，可以观察到dp[i]只依赖dp[i-1]，于是空间能压成 O(1)。这时候要特别注意变量更新顺序：必须先把旧值存下来，再算新值，否则同一天内会重复使用当天已经更新过的结果，逻辑错乱。这是我实际编码时反复栽过的地方。
class Solution { public: 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 newCash = max(cash, hold + prices[i]); int newHold = max(hold, cash - prices[i]); cash = newCash; hold = newHold; } return cash; } };这段代码的newCash和newHold就是典型的"先算后换"，虽然看起来多定义了两个变量，但能彻底杜绝"用新值算新值"的隐藏 bug。
3.3 手算一遍，理解状态转移的数值过程
很多新手看代码觉得简单，但一让手算就懵。以[7, 1, 5]为例，我演示一遍 DP 的推演过程。
第 0 天结束时：dp[0][0] = 0（不持有，没花钱也没赚钱），dp[0][1] = -7（持有，相当于花了 7 块钱买入）。
第 1 天价格 1：dp[1][0] = max(0, -7 + 1) = 0，意思是今天不持有，要么昨天就不持有，利润 0；要么昨天持有今天卖出，亏 6，显然不划算。dp[1][1] = max(-7, 0 - 1) = -1，意思是今天持有，要么昨天就持有继续扛，亏 7；要么昨天不持有今天花 1 买入，亏 1。显然今天买入比昨天买入更划算。
到了第 2 天价格 5：dp[2][0] = max(0, -1 + 5) = 4，今天不持有，最优路径是昨天持有、今天卖出，净赚 4。dp[2][1] = max(-1, 0 - 5) = -1，继续持有或者今天买入，都还是亏 1 最优。
所以最终答案是dp[2][0] = 4。这个手算过程特别能帮你理解为什么"买入利润是负数，卖出利润才转正"：持有状态本质上记录的是"买贵了多少钱"，等卖出时再把差价加进去。
3.4 为什么说 DP 是贪心的超集
你可能会问：122 题既然贪心几行就写完了，为什么还要费劲写 DP？因为 DP 得到的答案和贪心完全一致，但 DP 不依赖任何"局部最优全局最优"的假设，它把所有路径都枚举并筛选了一遍。换言之，贪心是 DP 在特殊限制下的特例：当交易次数无上限、无手续费、无冷冻期时，DP 的最优策略自然就是"每个上涨段都做一次买卖"，于是和贪心殊途同归。
面试时如果你能说出"贪心是构建在特定前提下的高效解法，DP 是更普适的框架"，就已经比只知道背代码的候选人高一个层次。
4. 变体扩展：手续费、冷冻期、交易次数上限
4.1 含手续费（714）：成本写进转移方程
714 题在无限次交易的基础上加了手续费，每次买卖要交fee元。做法很简单，在状态方程里把成本扣掉就行。我一般习惯在卖出时扣手续费：
class Solution { public: int maxProfit(vector<int>& prices, int fee) { int n = prices.size(); if (n < 2) return 0; int cash = 0; int hold = -prices[0]; for (int i = 1; i < n; ++i) { int newCash = max(cash, hold + prices[i] - fee); int newHold = max(hold, cash - prices[i]); cash = newCash; hold = newHold; } return cash; } };有人喜欢在买入时扣fee，方程变成newHold = max(hold, cash - prices[i] - fee)，数学上结果一样。但要注意：cash的初始值如果是 0，买入时扣费会让hold变成-prices[0] - fee，后续卖出时就不需要再扣。反正关键是一套代码里只能选一种扣法，混着用会导致每笔交易被重复扣两次手续费。我见过不止一个初学者栽在这个细节上。
4.2 含冷冻期（309）：状态从两个变成三个
309 题在无限次交易基础上加了"卖出后第二天不能买入"，也就是冷却 1 天。这时候"不持有"状态内部出现了分歧：我昨天刚卖出（今天注定不能买）和我昨天就没持有（今天可以买）。如果继续只用一个cash表示不持有，你无法区分"能不能买"，所以要把状态拆成三个：
hold：今天结束时手里持有股票；sell：今天结束时处于"因卖出而进入的冷冻期"，即今天刚卖了；rest：今天结束时既不持有、也不在冷冻期，随时可以再买。
转移方程有一个简单的版本：
int newHold = max(hold, rest - prices[i]); int newSell = hold + prices[i]; int newRest = max(rest, sell);解释一下：newHold要么继续持有旧股，要么在"可以买"的状态下买入；newSell只能由持有状态卖出产生；newRest要么保持原来的空仓，要么从冷冻期恢复。
实际编码时，我建议用一个三元素的long long数组做滚动，避免变量更新顺序出错。冷冻期题是整个系列里最容易把脑壳绕晕的一道，因为它让"空仓"这个状态不再单一，如果你只盯着二维 DP 的旧模型，很难一步到位想明白。
4.3 最多 K 次交易（188）：在状态上加交易次数维度
123 题要求最多交易两次，188 题把它推广到 K 次。这类题的做法是在基础 DP 上再增加一维记录"已经完成的交易次数"。我把状态定义成dp[j][0]和dp[j][1]，表示"已经完成 j 次交易，当前不持有 / 持有股票"时的最大利润。转移时，买入视为开启一次新交易，卖出不增加次数：
class Solution { public: int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if (n < 2 || k == 0) return 0; if (k >= n / 2) { // 退化为无限次交易 int profit = 0; for (int i = 1; i < n; ++i) { if (prices[i] > prices[i-1]) profit += prices[i] - prices[i-1]; } return profit; } vector<vector<int>> dp(k + 1, vector<int>(2, 0)); for (int j = 0; j <= k; ++j) dp[j][1] = INT_MIN / 2; for (int i = 0; i < n; ++i) { for (int j = 1; j <= k; ++j) { dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i]); dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]); } } return dp[k][0]; } };这里有几个容易踩的坑。第一，dp[j][1]初始化不能是 0，因为它表示"我持仓但没花任何成本买入"，这在现实中是不可能的；用INT_MIN又可能溢出，所以我习惯用INT_MIN / 2。第二，k >= n / 2时如果还坚持 O(k*n) 的 DP，数据一大容易超时，这时退化用贪心是常见优化手段。第三，遍历顺序上，内层j从小到大没问题，因为dp[j-1][0]用的是上一轮循环（前一天）的旧值，属于合法的转移。
4.4 一个状态机模板，串联六道题
把 121、122、714、309、123、188 放在一起看，你会发现它们都在做同一件事：定义有限个状态，描述状态之间的转移，按时间顺序递推。区别只在于状态个数和维度：
- 121 可以看作"禁止卖出后再买入"，所以只有持有/不持有两个状态；
- 122 就是基本两个状态；
- 714 两个状态 + 成本项；
- 309 三个状态；
- 123、188 状态维度 + 交易次数。
所以刷完整个系列后，我养成了一个习惯：遇到"某天结束时处于几种可能状态"的最优化问题，先画状态草图，再写转移方程，最后填代码。这套动作几乎能套进所有线性 DP 题。
4.5 各变体的复杂度对比
| 题号 | 时间复杂度 | 空间复杂度 | 关键状态数 |
|---|---|---|---|
| 121 | O(n) | O(1) | 2 个变量 |
| 122 | O(n) | O(1) | 2 个变量 |
| 714 | O(n) | O(1) | 2 个变量 + fee |
| 309 | O(n) | O(1) | 3 个变量 |
| 123 | O(n) | O(1) 或 O(n) | 2 次交易的 4 状态 |
| 188 | O(k*n) | O(k) | k+1 个交易次数维度 |
这张表能帮你一眼判断面试官会不会继续加难度。比如从 123 到 188，复杂度从 O(n) 涨到 O(k*n)，如果k非常大，就退化到无限次交易直接用贪心。这种"边界退化"思维，在算法优化里非常值钱。
5. 刷题实操中的常见错误与排查心得
5.1 边界条件：空数组、单元素数组
股票系列几乎每道题的入口都要处理prices.size() < 2的情况。小于 2 意味着没有交易机会，直接返回 0。如果你不做这个判断，后续prices[1]、prices[0]的访问直接越界，程序行为未定义。VSCode 里跑的话还可能弹出一堆看不懂的运行时错误。
我还见过一种隐蔽的问题：用INT_MIN作为极小值初始化状态时，在INT_MIN + prices[i]这类表达式上发生整数溢出。C++ 的 signed int 溢出是未定义行为，不同编译器结果都可能不一样。所以我个人更倾向于用INT_MIN / 2或者直接用long long来算利润，虽然题目说价格范围不大，但写习惯了能少踩很多雷。
5.2 初始化错误：dp[0][1] 究竟是 0 还是 -prices[0]
这是 DP 新手最容易犯的错误。dp[0][1]表示第 0 天结束后持有股票的最大利润，你只能靠第 0 天买入获得，所以应该是-prices[0]。如果初始化成 0，相当于告诉你"免费获得一股股票"，后面所有状态都会偏离正确答案。
我调试过不少次这种问题，症状是：无论输入什么数据，答案是 0 或者一个明显偏大的数。排查方法很简单，把前几天的dp数组打印出来对比一下手算结果，一眼就能看出初始化错了。
5.3 手续费重复计算
714 题里，如果你在买入时扣了一次fee，又在卖出时扣了一次，整体利润会凭空少了 n 笔手续费。这种错误在样例数据小的时候不一定暴露，但提交到大测试集就会 WA。我的建议是：写代码前先想清楚"手续费计入哪个动作"，然后在代码注释里写明。比如"卖出时扣 fee"，那么hold相关的买入转移就绝不能再减fee。
5.4 滚动变量的更新顺序
用滚动数组时，最常见的 bug 是原地更新导致当天状态被二次使用。比如cash = max(cash, hold + prices[i]); hold = max(hold, cash - prices[i]);，这里第二个式子里的cash已经是当天的新值，隐含允许了"当天卖出后当天再买入"，这在 122 这类无限次交易题里可能恰好结果一致，但在 309 冷冻期题里就会产生完全错误的答案。
解决方案有两个：要么像前面代码那样用newCash、newHold先算后赋；要么严格按依赖关系先算不依赖新值的那个。我推荐前者，可读性更好，也不容易出错。
5.5 在 VSCode 里调试 DP 的实操建议
股票系列我推荐用 VSCode 配置好 C++ 调试环境后，直接打断点看变量。具体说，把prices设成[7,1,5,3,6,4]，在dp[i][0]的赋值语句处打断点，单步执行，观察每个中间状态。这样能非常直观地把"状态到底是怎么从 0 变成 6 再变成 7"的全过程看清楚。
配置 C++ 环境的核心是写好tasks.json和launch.json，前者负责用 g++ 编译，后者负责启动调试器。很多初学者卡在这里，其实只要注意args里别漏掉-g调试参数就行。如果你平时刷题用洛谷或者其它在线评测，也可以先在本地把样例跑通，再提交验证。遇到runtime error，不要慌，多半就是边界没判。
5.6 常见问题速查表
| 症状 | 可能原因 | 排查方向 |
|---|---|---|
| 答案偏大 | 手续费重复扣除 / 初始化成 0 | 检查 fee 扣了几次 |
| 答案永远是 0 | 空仓状态没正确更新 | 检查 dp[j][1] 初始化 |
| 越界崩溃 | 没处理 n < 2 | 入口加边界判断 |
| 冷冻期答案错误 | 滚动变量更新顺序错乱 | 改用新变量先算后赋 |
| 188 超时 | k 太大导致 O(k*n) 过重 | 判断 k >= n/2 退化贪心 |
6. 从股票问题延伸到动态规划通识
6.1 线性 DP 的固定套路：状态、初始化、转移、遍历
股票问题其实是线性 DP 的典型例子。所谓线性 DP，就是状态沿着数组下标或者天数顺序往前推，每一步只依赖前一步的状态。这类题有固定套路：定义状态、确定初始化、写转移方程、决定遍历顺序、验证边界。
把股票题做完之后，你会突然发现"打家劫舍""最长递增子序列""编辑距离"这些经典题都在用同一套框架。区别只是状态的含义不同：股票题里是"持有与否"，打家劫舍里是"偷与不偷"，LIS 里是"以当前元素结尾的长度是多少"。如果你能在一道题里把五步走完，再去看其它 DP 题会轻松很多。
6.2 与 01 背包问题的本质联系
热词里有人提到 01 背包，其实它也跟股票题有很大渊源。01 背包的状态是dp[i][j]表示"前 i 个物品、容量为 j 时能装的最大价值"；股票 DP 的状态是dp[i][0/1]表示"第 i 天结束时处于某种持仓状态的最大利润"。两者都有一个共同点：当前状态由上一个状态决策推出，决策之间不能遗漏。
更具体地，01 背包的"选 / 不选"和股票题的"买 / 不买"、"卖 / 不卖"在结构上完全同构。学会了股票题的状态机，再去看背包问题的转移方程，你会觉得非常亲切。所以我一直建议新手把这两类题放在一起刷，互相印证。
6.3 面试中的快速判别：什么时候能贪心，什么时候必须 DP
我面试别人和准备面试时，总结过一个很实用的判断经验：
- 如果题目是"无限制交易 + 无额外成本 + 每次决策独立"，优先想贪心；
- 如果出现"交易次数上限 / 冷却期 / 手续费 / 关联限制"里的任何一项，基本就得上 DP。
这个判断不只在股票题里有效，在很多优化类题目里都适用。它背后的原理很简单：贪心成立的前提是"局部最优可以由简单规则直接拼接"，而一旦有限制条件，局部决策之间就有了复杂的相互制约，你必须靠 DP 的全局状态来消解这些制约。
6.4 刷题顺序与配套练习
股票系列的正确刷题顺序，我觉得应该是：
- 121（单次交易，理解最小值追踪）；
- 122（无限次，理解贪心与 DP 的等价）；
- 714（手续费，理解成本如何进方程）；
- 309（冷冻期，理解状态拆分）；
- 123（两次交易，理解交易次数维度）；
- 188（K 次交易，理解复杂度优化）。
这个顺序的好处是每一步都在上一步的基础上加一个限制条件，不会让你一上来就面对最复杂的 K 次状态。刷的时候不要急着看题解，先把状态定义写在纸上，再手算一个小例子验证。我在洛谷的动态规划题单里也刷过很多类似题目，经验是：动手推一遍比自己看十遍题解有效得多。
最后再分享一个我自己的体会。我第一次做 309 题时，一直想不通为什么需要第三个状态，后来把状态转移图画在纸上才豁然开朗。从那以后，只要遇到"一天结束时可能处于几种情况"的最优化问题，我第一件事就是画状态草图，再写转移方程。这个方法帮我把一堆看起来完全不相关的题目都串了起来。股票系列是练习这套方法论最好的入口之一，希望你也能顺着这条思路，把 DP 这块硬骨头真正啃下来。
