企业官网建设流程全解析

股票买卖问题，几乎每个刷过 LeetCode 的 C++ 学习者都会碰到。我一开始也觉得它就是个简单贪心题，后来才发现，同一道题换个限制条件，解法就从贪心切成了动态规划，甚至从二维 DP 涨到三维 DP。今天这篇笔记，专门把股票问题里动态规划和贪心算法分别怎么用、状态机怎么一步步推出来，以及 C++ 实现里那些一不留神就踩坑的地方讲清楚。适合刚开始入门 C++ 算法、准备机试或者面试的朋友，也适合那些把题解背下来了但换个变形就不会写的人。

很多人会问，动态规划和贪心算法到底有什么区别。股票问题恰好是解释这个问题的最佳切片：它能用贪心解决时，代码短到一行；需要 DP 时，又能把状态设计、状态转移、滚动数组、边界初始化这些基本功全练一遍。所以不要把这个系列当模板背，把它当成一组入门训练题来刷，收益会大得多。

1. 股票问题到底在考什么

1.1 一个输入数组，衍生出一整套题型

股票系列问题的底子非常统一：给你一个数组prices，prices[i]表示第 i 天的股票价格，假设你手上最多只能持有一股股票，并且资金无限，问最终能拿到的最大收益是多少。

真正让这个系列成为经典的是它的“限制条件”可以随意变化：

• 只能买卖一次：对应 LeetCode 121
• 可以无限次买卖：对应 LeetCode 122
• 最多只能完成两笔交易：对应 LeetCode 123
• 最多完成 k 笔交易：对应 LeetCode 188
• 卖出后第二天不能买入：对应 LeetCode 309
• 每次交易需要固定手续费：对应 LeetCode 714

为什么值得单独写一篇？因为这些题里的“状态”特别少，理论上只有“持有”和“未持有”两种，但由此引出的状态设计逻辑，覆盖了动态规划里最常见的套路。把这个系列吃透，后面再刷打家劫舍、背包问题、最长递增子序列这些题，你会明显感觉状态设计这一步没那么玄乎了。

这张表建议收藏，它把整个系列的最优思路和复杂度都列清楚了。注意 121 的扫描法和 122 的贪心虽然在代码上都不算 DP，但它们的逻辑来源其实都能从前面的 DP 状态转移式子里推出来，这也是这篇文章想强调的：先懂通用框架，再谈优化技巧。

1.2 为什么说先学会 DP，再学贪心

很多人的第一反应是，股票买卖不是贪心吗，为什么还要搞动态规划？这个想法坑过不少人。

贪心解决的是“无限次交易”这个特例，状态空间小，局部最优能推出全局最优。但只要加上交易次数限制、冷冻期或者手续费，简单贪心就不成立了。比如加了手续费后，每次都赚一个正差价可能还不够覆盖手续费，这时候必须用 DP 做全局权衡；加了冷冻期后，某天卖出后第二天不能买入，贪心没法处理这种“未来限制”。

动态规划就不一样。无论约束怎么加，你都可以在状态定义里多留一个维度：交易次数、冷冻状态、手续费，然后照着重写转移方程。所以我的建议是，刷入门阶段一定要先把 DP 框架吃透，贪心当作特例去记。这样面对变形题，你至少知道往哪个方向改，而不是对着题目发呆。

2. 动态规划破题：状态机模型与 C++ 实现

2.1 状态定义：先回答“今天结束时我在什么状态”

学 DP 的第一步永远不是急着抄转移方程，而是想清楚dp[i]到底记录什么东西。股票问题里，每个交易日结束，你只有两种身份：手里有股票，或者手里没有股票。

于是可以定义：

• dp[i][0]：第 i 天结束时不持有股票，能拿到的最大利润
• dp[i][1]：第 i 天结束时持有股票，当前账面上的最大利润

这里有个细节：dp[i][1]完全可以是负数，因为买入要花钱。比如第一天价格是 5，你买了股票，账上利润就是 -5，后面价格涨到 8，卖出后才变成 3。

为什么用“第 i 天结束时”而不是“第 i 天”？因为同一天你可能买入也可能卖出，如果不对“结束状态”做约束，转移方程里就会混入同一时刻的前后顺序问题。你可以把每天结束想成晚上盘点资产：钱包里有多少钱，账上有多少股票，然后第二天再做新的决定。

2.2 状态转移：不操作、买入、卖出三种选择

以无限次交易为例。第 i 天结束时，如果你不持股，有两种可能的来路：

1. 昨天结束就不持股，今天只是继续观望：dp[i-1][0]
2. 昨天结束持股，今天卖出走人：dp[i-1][1] + prices[i]

两者取最大，就是：

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

第 i 天结束时如果你持股，也有两种来路：

1. 昨天结束就持股，今天继续拿着：dp[i-1][1]
2. 昨天结束不持股，今天买入：dp[i-1][0] - prices[i]

所以：

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

买入为什么是dp[i-1][0] - prices[i]？因为买股票要花钱，现金减少。卖出为什么是dp[i-1][1] + prices[i]？因为持仓的价值按当天价格转换成现金。

到这里，状态机的骨架已经出来了。它本质上是在回答一个递归的问题：想拿到第 i 天的最优收益，只需要知道第 i-1 天两个状态的最优值。这就是动态规划“最优子结构”的体现。

2.3 先写二维数组，再压成一维变量

很多教程上来就给你滚动数组版本，但新手最好先从二维数组理解，确认自己真的看懂转移方程了，再优化。

C++ 实现可以先这么写：

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[n-1][0]？因为最后一天手里还持有股票，说明没卖，利润没有真正落袋；只有不持股的利润才是最终答案。

这个写法复杂度没问题，但空间上可以优化。因为每一天只依赖前一天，不需要保留整张二维表。压缩成两个变量：

int maxProfit(vector<int>& prices) { int n = prices.size(); if (n < 2) return 0; long long dp0 = 0; // 当前不持股最大利润 long long dp1 = -prices[0]; // 当前持股最大利润 for (int i = 1; i < n; ++i) { long long new0 = max(dp0, dp1 + prices[i]); long long new1 = max(dp1, dp0 - prices[i]); dp0 = new0; dp1 = new1; } return static_cast<int>(dp0); }

注意这里必须用new0和new1暂存旧值。如果直接写dp0 = max(...); dp1 = max(...);，第二行里的dp0已经是“今天”计算出的不持股利润，可能造成“今天卖出后立刻又买入”的错误更新。在无限次交易里这个错误不一定影响最终值，但在后面冷冻期、限制交易次数版本里会直接算错。养成先暂存、再统一更新的习惯，是纸笔 DP 改成代码 DP 的第一道门槛。

2.4 只允许一次交易：把“买入”条件收紧

如果是 LeetCode 121，只能买卖一次，转移方程要改一个地方。

在无限次交易中，买入用的是dp[i-1][0] - prices[i]，这意味着你在买入之前可能已经赚过钱，相当于拿着上一笔利润继续买，这就是“多次交易”的行为了。

只允许一次交易时，买入只能发生在还没开始赚钱的状态。换句话说，买入时的“本金”只有初始 0，所以：

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

这个式子的含义非常朴素：你已经买了的话就继续持有，还没买的话就看今天价格是不是历史最低，选一个最便宜的日子买入。

完整代码：

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

实际工程里这道题还可以直接扫描一遍维护最低价格，代码更短。但我还是建议你先理解这个 DP 版本，因为它是从“通用框架”收窄到“单次交易”的标准姿势，理解了它，面对变形题就不慌了。

3. 贪心算法：无限次交易的最优解

3.1 把交易拆成相邻两天的差价

当交易次数不受限制时，问题出现一个很强的性质：你不需要等到涨很多才卖。只要今天比昨天贵，你今天把昨天买的卖掉，赚到差价就是赚的。

换句话说，答案可以写成：

res = max(0, prices[1] - prices[0]) + max(0, prices[2] - prices[1]) + ... + max(0, prices[n-1] - prices[n-2])

为什么能这么拆？因为一次“从第 i 天买到第 j 天卖出”的长线交易，等价于把中间每一天的相邻差价全部累加。比如价格序列[1, 2, 3, 4]，你在第 1 天买、第 4 天卖，利润是 3；而相邻差价(2-1) + (3-2) + (4-3)也是 3。完全一样。

如果中间有跌价，比如[1, 3, 2, 4]，贪心的逻辑是把[1,2]和[2,3]的上涨段分别吃下：(3-1) + (4-2) = 4。你确实可以通过两次交易拿到 4，而且这个结果等于“跌前卖、跌后买”的自然操作。

3.2 贪心在这里为什么成立

贪心算法的前提是“局部最优能推出全局最优”。在无限次交易股票问题里，局部最优就是“遇到上涨就赚一笔”，而这个局部选择不会妨碍后面的交易。

你可以这样想：无论采用什么交易策略，最终收益都可以拆成若干个“买入价到卖出价”的区间。每个区间拆成相邻差价的累加后，只要有一段是负的，把它从总收益里去掉只会让结果更好。所以把所有正差价全部保留，就是最优解。

这个思路比死记“只要涨就卖”要可靠得多。面试的时候如果被问到贪心为什么正确，你不需要背标准答案，把“区间收益可拆分、负差价可省略”这两句话讲清楚，基本就过关了。

3.3 C++ 实现：一行代码和它的边界条件

贪心写出来比 DP 短得多：

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

也可以写成res += max(0, prices[i] - prices[i-1]);，需要包含<algorithm>。

边界条件就一个：prices为空或者只有一个元素，循环根本不会执行，直接返回 0，所以这个写法天然安全。

但要注意，贪心只在“无限次交易 + 无手续费 + 无冷冻期”时才这么简单。加了手续费，每次交易都有成本，见涨就卖可能把利润全赔给手续费；加了冷冻期，卖出后的买入被推迟，贪心不再成立。所以面试时如果问你“为什么这题能贪心，别的变形不贪心”，你最好从这个角度回答。

4. 题型变形：冷冻期、手续费与最多 K 次

4.1 含冷冻期：两个状态不够，升级到三个状态

LeetCode 309 在无限次交易基础上加了一条：卖出股票后，第二天不能再买入。这个限制直接打破了“持有”和“不持有”两状态循环，因为“不持有”里还要区分“今天能不能买”。

我习惯用三个状态：

• sell：第 i 天结束时，刚卖出，进入冷冻期
• rest：第 i 天结束时，不持股且不在冷冻期
• hold：第 i 天结束时，持股

转移关系：

• 今天卖出，那昨天一定持股：newSell = hold + prices[i]
• 今天不持股且非冷冻，要么昨天就是 rest，要么昨天冷冻今天解冻：newRest = max(rest, sell)
• 今天持股，要么昨天持股继续持有，要么昨天不持股非冷冻买入：newHold = max(hold, rest - prices[i])

代码：

int maxProfit(vector<int>& prices) { int n = prices.size(); if (n < 2) return 0; int sell = 0; // 刚卖出，冷冻 int rest = 0; // 不持股，可以买 int hold = -prices[0]; // 持股 for (int i = 1; i < n; ++i) { int newSell = hold + prices[i]; int newRest = max(rest, sell); int newHold = max(hold, rest - prices[i]); sell = newSell; rest = newRest; hold = newHold; } return max(sell, rest); }

注意newHold里用的是旧的rest，不是更新后的rest。如果你不暂存，让rest先更新，再用新rest去算hold，可能会在一天内做“先买入再卖出”之类的错误操作。这个坑和前面 DP 更新顺序的坑一模一样。

4.2 含手续费：每笔交易扣一次成本

LeetCode 714 在无限次交易基础上加一个手续费。手续费可以在买入时扣，也可以在卖出时扣，但只能扣一次。我习惯在卖出时扣：

• 不持股：max(昨天不持股, 昨天持股 + 价格 - 手续费)
• 持股：max(昨天持股, 昨天不持股 - 价格)

代码：

int maxProfit(vector<int>& prices, int fee) { int n = prices.size(); if (n < 2) return 0; long long dp0 = 0; long long dp1 = -prices[0]; for (int i = 1; i < n; ++i) { long long new0 = max(dp0, dp1 + prices[i] - fee); long long new1 = max(dp1, dp0 - prices[i]); dp0 = new0; dp1 = new1; } return static_cast<int>(dp0); }

加了手续费后，贪心为什么不能用？因为每次交易都要付出固定成本，可能出现一种情况：今天赚到的差价小于手续费，表面是赚，实际整体亏。DP 会把“今天卖不卖”的长期影响一起算进去，所以它能判断什么时候应该忍住不交易。

这里还有一个易错点：手续费千万别既在买入时扣一次，又在卖出时扣一次。要扣就在转移方程里统一写一个位置。

4.3 最多 K 次交易：三维状态和初始化陷阱

LeetCode 188 把交易次数限制到 k。这个时候需要在原来的二维状态上再加一维，记录已经完成的交易次数。

设dp[i][j][0]表示第 i 天结束时，已经完成 j 笔交易，并且不持股；dp[i][j][1]表示第 i 天结束时，已经完成 j 笔交易，并且持股。

这里最关键的是定义“完成一笔交易”的时机。大多数题解把“卖出”作为一笔交易完成的标志，也就是交易次数在卖出时加一。买入时不加。

转移方程：

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

第二个式子里，从“不持股”到“持股”是在买入，交易次数没有增加，所以下标仍然是 j。如果你把买入和卖出都算一次交易，一买一卖就会记成两笔，结果全错。

初始化时，所有状态先设为负无穷，避免取到“从未发生”的情况。只有dp[0][0][0] = 0和dp[0][0][1] = -prices[0]是合法起点。

C++ 里可以用滚动数组压掉 i 维度：

int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if (n < 2 || k == 0) return 0; // 实际最多只能完成 n/2 笔交易，超过就退化成无限次 if (k > n / 2) { int res = 0; for (int i = 1; i < n; ++i) { if (prices[i] > prices[i - 1]) res += prices[i] - prices[i - 1]; } return res; } const int NEG = -1e9; vector<int> dp0(k + 1, NEG), dp1(k + 1, NEG); dp0[0] = 0; dp1[0] = -prices[0]; for (int i = 1; i < n; ++i) { vector<int> ndp0(dp0), ndp1(dp1); for (int j = 0; j <= k; ++j) { if (j > 0) { ndp0[j] = max(ndp0[j], dp1[j - 1] + prices[i]); } ndp1[j] = max(ndp1[j], dp0[j] - prices[i]); } dp0 = ndp0; dp1 = ndp1; } int ans = 0; for (int j = 0; j <= k; ++j) { ans = max(ans, dp0[j]); } return ans; }

为什么k > n/2时要退化？因为一次完整的交易至少需要买入和卖出两天，n 天里最多完成 n/2 笔交易。如果 k 比这个还大，限制就是虚的，直接返回无限次交易的最优解就行。这个优化不仅能防止多余的循环，还能避开一些初始化的边界问题。

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

5.1 空输入、越界与初始化错误

股票问题最常见的三个错误：

1. 数组为空或只有一个元素，没有提前返回，导致访问prices[0]越界。
2. 初始化时dp1设成 0，而不是-prices[0]。如果设成 0，第一天的持股利润被高估，后续所有转移都会受影响。
3. 三维 DP 里把“买入”也计入交易次数，导致一笔买卖被记成两笔。

尤其是第 2 个错误，初期很容易犯。你可以这样记：只要状态里表示“持有股票”，第一天买入后手上的现金一定是负数，所以初始值必须是-prices[0]，而不是 0。

5.2 更新顺序：为什么必须暂存旧值

我在前文反复提暂存new0、new1，因为这个坑太典型了。二维数组版本里，dp[i]依赖dp[i-1]，天然安全；一旦压缩成两个变量，依赖关系就不明显了。

错误写法：

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

第二行里dp0已经被更新成当天的值，继续用它去计算dp1，相当于在同一天里先卖后买，状态机被绕晕了。正确做法永远是先把旧值都保存好，再统一更新所有状态。

判断自己有没有踩这个坑，可以拿一个简单样例手算：[1, 2, 3]，正确结果是 2。错误更新会得到 3，因为你在第二天卖出再买入，相当于把低价重复利用了一次，这在无限次交易模型里恰好也能解释通，但在带限制的版本里就非常致命。

5.3 手算样例调试法：不要再靠眼神找 bug

写 DP 题最怕的就是数组越界和状态错乱。我自己的排查习惯是找一组短样例，手动在纸上推进状态。比如用[1, 3, 2, 4]跑一遍无限次交易的两状态 DP：

• 第一天结束：不持股 0，持股 -1
• 第二天结束：不持股 2，持股 -1
• 第三天结束：不持股 2，持股 1
• 第四天结束：不持股 4，持股 1

答案是 4。你再拿贪心跑一遍，(3-1)+(4-2)=4，两边一致。这种“两个解法结果对照”的方法，比盯着屏幕看强得多。如果哪天实现有问题，手算结果就能帮你定位到底是最初值错了、转移错了，还是更新顺序错了。

5.4 面试追问：从“会做”到“能讲”

刷股票问题的最终目的不只是 AC。面试官最喜欢在这个题后面追加几个问题：

• 只允许一次交易，你的代码最少要改几行？
• 无限次交易的贪心怎么证明？
• 如果允许输出具体买卖点，你怎么改？
• 为什么要冷冻期不能用简单两状态？
• 交易次数限制为 k，复杂度能不能优化到 O(n)？

最后一个问题有技巧。dp0[j] - prices[i]在遍历 j 时，可以与dp0[j]一起在上一轮计算中维护最值，从而把内层 k 循环优化掉，但那是另一个层面的进阶问题。入门阶段先保证你能把三维 DP 写对，再去谈优化，不要一步登天。

我自己刷这几题时的习惯是，把所有变形题放在同一天刷完，然后统一写一篇笔记。每道题先按“二维数组版”写一遍，体会状态；再改成“滚动数组版”，体会空间优化；最后尝试用贪心或扫描写一遍，看看能不能推出更短的代码。这样一轮下来，你对动态规划状态转移的理解会比刷十道不相关的题更扎实。

说到底，股票问题的本质不是教你炒股，而是让你学会用状态机描述决策过程。DP 不是魔法，贪心也不是万能。你只要能把“今天结束时我在什么状态、我从哪些状态过来”这两句话想明白，这类题就很难再难住你。下一回遇到换房子、跳台阶、抢银行之类的变形，你也可以用同样一套思路去拆解：先定义状态，再写转移，最后抠边界。