从LeetCode那个经典的股票系列开始说。股票买卖问题应该是很多C初学者第一次直观感受到同一个场景两种截然不同的解法的入口。场景一句话就能说清给你一个数组pricesprices[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只能买卖一次最小值追踪 / 简单DP122可无限次买卖贪心累计上涨段123最多买卖两次三维DP状态188最多买卖 K 次状态维度 1309卖出后有一天空仓期冷冻期三状态状态机714每次交易收手续费成本入方程这个表格是我每次给新手讲股票题必画的东西。原因很朴素你刷题如果只刷一道 121可能觉得这题水得很但如果把六道连在一起看你会发现它们其实是同一棵树上长出来的六个分支区别只在于限制条件而这些限制条件会直接影响状态设计。理解这一点有个额外的好处你不会再觉得动态规划好难、我看不懂——因为当你能把六道题的状态定义和转移方程整齐地列出来时它们就不再是六道孤立的题而是一套可以互相印证的体系。1.3 两种算法思维的分水岭贪心和 DP 各管哪一段简单说贪心算法强调的是每一步都做当前看起来最优的选择它假设局部最优能累积成全局最优动态规划则强调枚举所有可能状态通过状态转移吸收历史信息它不依赖局部最优假设只依赖状态定义的完备性。股票题目里这两者的分界线非常清晰。无限次交易、没有手续费、没有冷冻期时贪心成立一旦加入交易次数上限手续费冷冻期这类限制贪心的局部最优假设就会被打破。所以面试时如果让我选解法我会先看限制条件再决定上贪心还是 DP。2. 贪心算法先把最简单的解写出来2.1 只买卖一次用两个变量完成线性扫描121 题的最佳解法其实叫最小值追踪法思路非常直观。我遍历价格数组时维护两个变量minPrice到目前为止出现过的最低价格maxProfit到当前天为止如果卖出能得到的最大利润。每天的行情来了之后先更新minPrice因为日子越靠后的低点越可能是未来的买入点然后计算如果今天卖出能赚多少再更新maxProfit。这段代码极其精简class Solution { public: int maxProfit(vectorint 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(vectorint 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每天低买高卖累计是 11114结果完全一样。这个结论背后是无限次交易 无手续费这两个前提交易次数不花钱所以交易得越频繁越好而所有正差价之和恰好等于把所有上涨波段的涨幅全部收入囊中。反过来如果遇到下跌段你只要不持有就行不需要做任何操作。写这段代码时我踩过一个脑残坑if (prices[i] prices[i-1])我一开始写成了结果遇到连续两天价格相同的情况也累加差价利润凭空多出 0。虽然结果不影响0 加不加都一样但逻辑上不干净面试时被追问会显得不够严谨。2.3 贪心的边界什么时候有涨就吃会失效你必须清楚地知道贪心解法的适用边界。最简单的一个反例是加手续费的情况假设每天价格是[1, 2, 3]每次交易手续费 2 元。用贪心的思路第 1 天买第 2 天卖赚2-11扣掉手续费 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 天交易结束、手里持有一股时的最大利润持有股票时利润为负数因为它占用了现金。转移方程是两个maxdp[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(vectorint prices) { int n prices.size(); if (n 2) return 0; vectorvectorint dp(n, vectorint(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(vectorint 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 天价格 1dp[1][0] max(0, -7 1) 0意思是今天不持有要么昨天就不持有利润 0要么昨天持有今天卖出亏 6显然不划算。dp[1][1] max(-7, 0 - 1) -1意思是今天持有要么昨天就持有继续扛亏 7要么昨天不持有今天花 1 买入亏 1。显然今天买入比昨天买入更划算。到了第 2 天价格 5dp[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(vectorint 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, vectorint 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; } vectorvectorint dp(k 1, vectorint(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 各变体的复杂度对比题号时间复杂度空间复杂度关键状态数121O(n)O(1)2 个变量122O(n)O(1)2 个变量714O(n)O(1)2 个变量 fee309O(n)O(1)3 个变量123O(n)O(1) 或 O(n)2 次交易的 4 状态188O(k*n)O(k)k1 个交易次数维度这张表能帮你一眼判断面试官会不会继续加难度。比如从 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两次交易理解交易次数维度188K 次交易理解复杂度优化。这个顺序的好处是每一步都在上一步的基础上加一个限制条件不会让你一上来就面对最复杂的 K 次状态。刷的时候不要急着看题解先把状态定义写在纸上再手算一个小例子验证。我在洛谷的动态规划题单里也刷过很多类似题目经验是动手推一遍比自己看十遍题解有效得多。最后再分享一个我自己的体会。我第一次做 309 题时一直想不通为什么需要第三个状态后来把状态转移图画在纸上才豁然开朗。从那以后只要遇到一天结束时可能处于几种情况的最优化问题我第一件事就是画状态草图再写转移方程。这个方法帮我把一堆看起来完全不相关的题目都串了起来。股票系列是练习这套方法论最好的入口之一希望你也能顺着这条思路把 DP 这块硬骨头真正啃下来。