刷 LeetCode 刷到买卖股票的最佳时机这题的时候我第一反应是这不就是找最低点买入、最高点卖出嘛随手一个双重循环就交了。结果 WA 之后看了眼评论区才发现这原来是一整个家族买卖一次、买卖无数次、最多两次、最多 K 次、带手续费、带冷冻期。每一道题看起来差不多但解法从贪心一路升级到三维动态规划恰好是算法面试里状态机 DP 的最佳入门素材。这篇文章我就用 C 把这个系列完整地拆一遍把我自己踩过的坑、优化过的写法、还有在本地环境编译运行时碰到的各种奇奇怪怪的问题全部记录下来希望对正在刷这道题的人有点帮助。1. 这个系列到底在考什么从一行代码到状态机 DP1.1 一道题的多个变体121/122/123/188/309/714先说一个你可能也遇到过的情况第一次看买卖股票的最佳时机 II发现题解只有几行代码甚至比第一题还短。那时候我产生了严重的自我怀疑——难道第一题我写错了后来才意识到这个系列根本不是同一个题的难度递进而是六个不同的建模问题。题号约束条件核心思路时间复杂度121只能买卖一次维护历史最低价O(n)122可以买卖无数次贪心累加正利润O(n)123最多买卖两次分段状态机 DPO(n)188最多买卖 K 次三维 DP 滚动数组O(n*k)309含冷冻期三态状态机O(n)714含手续费状态机加扣费O(n)你会发现121 最简单122 反而比 123 简单得多。原因在于可以无限次交易这个约束让问题退化成了每天都可以结算利润而最多两次交易逼迫你必须记录当前是第几次交易这就引入了维度的概念。理解了这一点整个系列的学习路径就清晰了先掌握持有/不持有两种状态再往里面加入交易次数冷冻期手续费这些附加维度。1.2 两个核心变量的拆解交易次数与持有状态所有的股票问题本质上都是在问你今天的决策到底由哪些信息决定我把它们拆成两个变量第一当前是第几笔交易。每一笔交易的完整定义是一次买入 一次卖出买入时交易次数增加卖出时交易才算完成。第二当前是否持有股票。只有未持有才能买入只有持有才能卖出。这两个变量互相独立却共同决定了状态空间的大小。买卖一次的 121 题只需要是否持有最多买卖 K 次的 188 题则需要同时记录已进行到第几笔和是否持有于是状态数就是(K1) * 2。这就是为什么 188 题看起来是六道题里最复杂的——它的状态空间最大代码量自然最多。1.3 什么时候用贪心什么时候必须上 DP我最早犯的错误就是用 121 题的思路去套 122 题先找个最低点再找个最高点然后重复。运行出来结果不对之后我才认真想了一个问题为什么 121 可以只用一次扫描解决而 122 却需要每天都考虑买卖关键区别在于交易次数限制是否改变了决策的局部性。122 题没有次数限制所以每一天都可以独立判断今天比昨天贵我就假装昨天买了今天卖这段利润和前后天没有任何关联于是贪心成立。121 题只能交易一次你今天的决策会影响后续所有决策的组合这时候就必须动态规划来维护状态。个人经验看到最多 K 次这个表述优先把思路往 DP 上靠别在贪心上浪费时间。2. 基础版一次交易的扫描法C 边界处理细节2.1 维护历史最低价而不是差分数组121 题的经典解法不是从前向后找最大值也不是从后向前找最小值而是遍历时维护一个minPrice变量表示到当前位置为止出现过的最低价格。每次遇到更高的价格就结算一次当前价格减历史最低价的利润取最大值。#include vector #include algorithm class Solution { public: int maxProfit(std::vectorint prices) { int n static_castint(prices.size()); if (n 2) { return 0; } int minPrice prices[0]; int maxProfit 0; for (int i 1; i n; i) { if (prices[i] minPrice) { minPrice prices[i]; } else if (prices[i] - minPrice maxProfit) { maxProfit prices[i] - minPrice; } } return maxProfit; } };为什么要维护minPrice而不是维护一个差分数组prices[i] - prices[i-1]的累加因为只能交易一次要求你找到一个区间[buyDay, sellDay]使prices[sellDay] - prices[buyDay]最大。差分数组的累加适合无限次交易的场景而一次交易的区间利润无法由若干相邻差的简单累加直接得出。维护最小值本质上等价于对每个卖出日都去配对历史最佳买入日这是一种线性扫描 历史最优的典型套路。2.2 空数组、单元素、int 溢出容易被忽略的防御性编程第一次提交时我只写了主循环没有判空LeetCode 直接给我报了一个 access violation。从那以后我养成了一个习惯凡是对数组做首元素访问的算法第一行永远是判空和长度检查。if (n 2) { return 0; }n 2这个条件同时覆盖了空数组和单元素数组——空数组取不到prices[0]单元素数组无论如何都不能完成一次买卖利润必然为 0。这个写法比n 0的单独判断更紧凑也避免了一个很容易犯的顺序错误先访问prices[0]再判断n 0顺序反了依然会崩溃。关于 int 溢出绝大多数 LeetCode 测试用例用 32 位 int 完全没问题因为价格通常在 0 到 10^4 之间差值不超过 10^4。但这个系列里一旦引入手续费和K 次交易的复杂状态转移中间变量可能会出现负数比如用INT_MIN表示不可能持有股票的状态。这时候如果不注意INT_MIN prices[i]的溢出行为程序可能在本地跑得好好的提交后却出现诡异的错误。我自己的惯例是涉及明确的上下界时用std::max/std::min去夹逼避免做无意义的减法。2.3 为什么这个版本不能直接推广到 K 次有了 121 题的成功经验我试过把 121 的解扩展成 K 次遍历整个数组每次找到一段上升区间就累加。这个伪贪心在 122 题是可以的但在 123 题和 188 题不行因为最多 K 次意味着我要做的是选 K 段互不重叠的利润区间并让总和最大。如果直接贪心地选最高的 K 段上升区间区间之间可能重叠也可能因为选择当前最高段而错过了组成更高总和的方案。这个问题就必须用带交易次数维度的 DP 来解而不是在单次交易遍历上打补丁。3. 无限次交易贪心的正确性与 C 实现3.1 相邻差值和把交易拆成可重叠的段122 题我一直记得一句非常形象的话与其说我们在做买卖不如说我们在把每天的价格变化拆成无数个小段凡是上涨的小段都收入囊中凡是下跌的小段都不碰。int maxProfit(std::vectorint prices) { int profit 0; for (int i 1; i static_castint(prices.size()); i) { if (prices[i] prices[i - 1]) { profit prices[i] - prices[i - 1]; } } return profit; }严谨一点的证明思路是这样的任意一次完整交易[buy, sell]的利润都可以拆成prices[sell] - prices[buy] (prices[buy1] - prices[buy]) (prices[buy2] - prices[buy1]) ... (prices[sell] - prices[sell-1])因为无限次交易不受次数限制我们可以把一次跨越多个交易日的长交易拆成若干相邻交易日的短交易总利润不变。于是每天只需要判断相邻两天是否涨价涨价就累加跌价就无视。这就是贪心正确性的核心全局最优解可以完全由局部决策堆叠而成而不需要跨天协调。3.2 accumulate 与手写循环的取舍有人问我既然 122 题是累加相邻正差为什么不直接用 C 标准库的std::accumulate比如#include numeric int maxProfit(std::vectorint prices) { int profit 0; for (int i 1; i prices.size(); i) { profit std::max(0, prices[i] - prices[i - 1]); } return profit; }真要用 accumulate 也能写但要配合 lambda 捕获前一个元素int maxProfit(std::vectorint prices) { if (prices.empty()) return 0; int profit std::accumulate( prices.begin() 1, prices.end(), 0, [prev prices[0]](int acc, int cur) mutable { int delta cur - prev; prev cur; return acc std::max(0, delta); } ); return profit; }这个写法是可行的但我个人不推荐在面试或笔试中用。原因有两个第一lambda 里的mutable捕获对很多初学者来说不直观报错时容易懵第二笔试环境里的编译器版本不确定C20 之前对 lambda 捕获的语法支持差异可能导致编译失败。手写一个简单 for 循环可读性更好也没有任何性能劣势因为std::accumulate并不会帮你做向量化或并行化。3.3 从贪心到通用状态机的桥接贪心解法固然简洁但它是只适用于无限次交易的局部最优策略。一旦你尝试把交易次数限制为 K 次贪心立刻失效必须回到状态机 DP。这里给大家一个我在学习时体会很深的桥接点考虑两个变量cash和hold。cash表示当前不持有股票的最大现金余额。hold表示当前持有股票的最大现金余额。初始状态cash 0hold -prices[0]。每天的状态转移是cash max(cash, hold prices[i]) hold max(hold, cash_prev - prices[i])这个框架可以推广到 188 题、309 题和 714 题只是增加相应维度。因为它不依赖无限次交易这个前提而是显式地追踪每一笔交易的开始和结束。可以说贪心是状态机在特殊约束下的退化形式。4. 最多 K 次交易三维 DP、滚动数组、缓存局部性4.1 DP 定义与转移方程188 题是系列里最硬核的一题。题目要求最多完成 K 笔交易求最大利润。状态定义如下dp[i][j][0]表示第 i 天结束时已经完成了 j 笔交易当前不持有股票的最大利润。dp[i][j][1]表示第 i 天结束时已经完成了 j 笔交易当前持有股票的最大利润。这里的已经完成 j 笔交易有一个坑很多人会把买入时 j 加一和卖出时 j 加一搞混导致结果差一笔交易。我建议统一口径买入时交易次数增加卖出时交易次数不变。也就是说当你想从不持有转到持有时这意味着开启了一个新的交易周期j要加一。卖出只是把这个周期结算掉j不再变化。转移方程不持有卖出 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])第二个方程里dp[i-1][j-1][0] - prices[i]的含义是昨天完成 j-1 笔交易且不持有股票时今天买入开启第 j 笔交易。这保证了交易次数从 j-1 平移到 j。初始化部分dp[0][0][0] 0dp[0][j][1]在j 0时表示还没有任何交易就持有股票这在逻辑上是非法状态通常初始化为INT_MIN表示不可达防止它参与 max 比较。三维数组的完整 C 实现可以是#include vector #include algorithm #include climits class Solution { public: int maxProfit(int k, std::vectorint prices) { int n static_castint(prices.size()); if (n 2) { return 0; } // 实际能完成的最大交易次数不可能超过 n/2因为每次交易至少买入和卖出两天 k std::min(k, n / 2); std::vectorstd::vectorstd::vectorint dp( n, std::vectorstd::vectorint(k 1, std::vectorint(2, 0))); for (int j 0; j k; j) { dp[0][j][1] INT_MIN; // 第 0 天不可能持有股票除了买入 } dp[0][0][1] -prices[0]; // 第 0 天买入完成 0 笔交易后持股 dp[0][0][0] 0; for (int i 1; i n; i) { for (int j 0; j k; j) { // 不持有今天不操作或卖出 dp[i][j][0] std::max(dp[i - 1][j][0], dp[i - 1][j][1] prices[i]); if (j 0) { // 持有今天不操作或从 j-1 笔交易的不持股状态买入 dp[i][j][1] std::max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]); } else { dp[i][j][1] std::max(dp[i - 1][j][1], INT_MIN); } } } int ans 0; for (int j 0; j k; j) { ans std::max(ans, dp[n - 1][j][0]); } return ans; } };注意一个很实用的优化k std::min(k, n / 2)。因为一次完整的交易至少要经历买入、卖出两个交易日所以最多能完成的交易次数不可能超过n / 2。这个优化在 n 很小、k 很大的场景下能把状态空间缩小一个量级避免无谓的内存和循环。4.2 两层循环的方向为什么 j 要倒序如果完全用三维 DP空间复杂度是 O(n*k)在 n100000、k100000 时直接爆炸。经典优化是用滚动数组把第一维压掉只保留昨天和今天两个状态。这时候一个非常容易踩的坑是内层循环的方向。看下面这段错误的滚动数组实现for (int i 1; i n; i) { for (int j 1; j k; j) { dp[j][0] std::max(dp[j][0], dp[j][1] prices[i]); dp[j][1] std::max(dp[j][1], dp[j - 1][0] - prices[i]); } }问题出在哪里在于dp[j][0]更新之后紧接着的dp[j][1]会用到这个新的dp[j][0]。在二维滚动、状态间存在耦合的模型里dp[j][1] max(dp[j][1], dp[j-1][0] - prices[i])需要的是更新当天之前的dp[j-1][0]还是更新当天之后的dp[j-1][0]正确答案是后者。因为买入发生在卖出之前同一天的买入应该基于当天卖出完成后的利润。如果我们正序遍历 jdp[j][1]可能会用到已经被prices[i]更新过的dp[j-1][0]导致在同一天里既卖出又买入这等于把同一天当作两个交易日来用结果会偏大。所以 j 必须倒序遍历for (int i 1; i n; i) { for (int j k; j 1; --j) { dp[j][0] std::max(dp[j][0], dp[j][1] prices[i]); dp[j][1] std::max(dp[j][1], dp[j - 1][0] - prices[i]); } }倒序遍历的核心逻辑是更新dp[j][1]所需的dp[j-1][0]必须来自昨天而不是今天。从 k 往 1 走时dp[j-1][0]还没被今天的卖出逻辑更新过因此它仍然保持昨天的值。这是一个很多教程没有展开讲、但实际笔试很容易翻车的点。4.3 空间优化的 C 实现对比与测试结果做了滚动数组之后空间复杂度从 O(n*k) 降到 O(k)。进一步优化可以发现dp[j][0]和dp[j][1]可以拆成两个独立的一维数组cash[j]和hold[j]避免vectorvectorint的两次间接寻址class Solution { public: int maxProfit(int k, std::vectorint prices) { int n static_castint(prices.size()); if (n 2) { return 0; } k std::min(k, n / 2); std::vectorint cash(k 1, 0); std::vectorint hold(k 1, INT_MIN); for (int i 0; i n; i) { for (int j k; j 1; --j) { cash[j] std::max(cash[j], hold[j] prices[i]); hold[j] std::max(hold[j], cash[j - 1] - prices[i]); } } return cash[k]; } };手里没有专业 profiling 工具但我在本地的随机大数据测试里对比过两种写法vectorvectorint和两个独立vectorint的耗时差距大约在 10% 到 20% 之间。原因在于vectorvectorint的内存布局是外层 vector 存内层 vector 的指针访问dp[j][0]和dp[j][1]时要经历两次指针间接跳转缓存命中率偏低而两个独立一维数组每次访问都是直接地址连续性好很多。这里分享一个我自己做性能对比时用的方法生成 n100000、k100000 的随机价格序列在开启-O2优化的情况下分别跑十次取平均值。注意输出中间结果会被编译器优化掉必须把结果累加到一个volatile变量里或者直接打印出来否则可能出现两版都快得离谱的假象。5. 带手续费与冷冻期的变体状态机建模5.1 手续费扣在买入还是卖出714 题在 122 题的基础上加了一个手续费fee每次交易完成后要交一笔固定费用。有两种等价处理方式买入时扣除手续费或者卖出时扣除手续费。我在代码里习惯写成买入时扣除class Solution { public: int maxProfit(std::vectorint prices, int fee) { int n static_castint(prices.size()); if (n 2) { return 0; } int cash 0; // 不持有股票的最大利润 int hold -prices[0] - fee; // 持有股票已经扣过手续费 for (int i 1; i n; i) { int prevCash cash; cash std::max(cash, hold prices[i]); hold std::max(hold, prevCash - prices[i] - fee); } return cash; } };为什么建议扣在买入而不是卖出因为这样可以保证hold变量始终代表当前持有这只股票的全部成本后续比较是否换股时不需要在卖出时反复加减手续费代码更简洁。而且从建模角度讲交易成本在开启交易的一瞬间就产生了更符合直觉。一个容易出错的地方是hold std::max(hold, prevCash - prices[i] - fee)里的prevCash用的是更新前的cash而不是更新后的cash。如果直接写cash - prices[i] - fee当天就可能出现先卖出再买入的重复交易手续费也被算了一次。这个坑和 188 题里 j 的倒序是同源的。5.2 冷冻期三态之间的转移309 题在 122 题的基础上规定卖出股票的第二天不能买入进入冷冻期第三天才能恢复。这个约束无法用持有/不持有两态简单表示因为不持有还分刚卖出处于冷冻期和可以自由买入两种子状态。所以需要三态状态 0不持有股票且处于冷冻期当天刚卖出。状态 1不持有股票且不在冷冻期可以买入。状态 2持有股票。状态转移状态 0 只能由昨天持股并卖出转移而来 dp[i][0] dp[i-1][2] prices[i] 状态 1 可以由昨天的状态 0 或状态 1 转移而来 dp[i][1] max(dp[i-1][0], dp[i-1][1]) 状态 2 可以由昨天持股不操作或昨天状态 1 买入转移而来 dp[i][2] max(dp[i-1][2], dp[i-1][1] - prices[i])对应 C 代码class Solution { public: int maxProfit(std::vectorint prices) { int n static_castint(prices.size()); if (n 2) { return 0; } // dp0: 不持股且冷冻 // dp1: 不持股且非冷冻 // dp2: 持股 int dp0 0; int dp1 0; int dp2 -prices[0]; for (int i 1; i n; i) { int newDp0 dp2 prices[i]; int newDp1 std::max(dp0, dp1); int newDp2 std::max(dp2, dp1 - prices[i]); dp0 newDp0; dp1 newDp1; dp2 newDp2; } return std::max(dp0, dp1); } };写成一个std::arrayint, 3而不是三个独立变量也可以但从可读性上讲独立命名dp0/dp1/dp2更直观面试时不容易说错。需要注意的是三变量之间不能原地更新必须先用新变量存好再一次赋值否则dp0更新后会影响dp2的计算产生同一天卖出又买入的错误。这个错误我在前几次写 309 题时反复出现后来养成了任何滚动状态都先算临时变量的习惯才彻底解决。5.3 常数空间版本代码上面 309 题的代码已经是常数空间了。很多人看到 dynamic programming 以为一定有二维数组其实最优的 DP 往往可以用几个变量完成因为状态转移只依赖昨天。如果你在面试中先写出二维数组版本再主动优化成常数空间会是非常加分的加分项。714 题的手续费版本也是常数空间。到这里你会发现整个系列的最优解空间复杂度基本都是 O(1) 或 O(k)只有 188 题因为引入交易次数维度空间复杂度才会上升到 O(k)。这可以说是一个规律状态机的状态数量决定空间复杂度上限滚动数组只是把状态从每一天一份压缩成只存昨天。6. 实操总结本地环境、编译优化与面试建议6.1 VS Code 下配置 C 编译环境与常见坑刷题归刷题很多人的 C 本地环境配置问题其实比算法本身还折腾。我见过好几个初学者卡在 VSCode 能写代码但无法编译运行 这一步最后直接放弃了。这里分享一下我的配置思路。在 Windows 上用 VS Code 写 C 最省心的组合是 MinGW-w64 VS Code C/C 插件。MinGW-w64 提供了 g 编译器VS Code 的任务系统负责编译和运行。安装时最好直接下载 x86_64-posix-seh 版本的压缩包手动解压后把bin目录加到系统 PATH。不要用在线安装器国内网络经常下到一半失败。配置.vscode/tasks.json时核心就是让 VS Code 调用 g 编译当前文件{ version: 2.0.0, tasks: [ { label: C 编译运行, type: cppbuild, command: g, args: [ -stdc17, -O2, -Wall, ${file}, -o, ${fileDirname}/${fileBasenameNoExtension}.exe ], group: { kind: build, isDefault: true }, problemMatcher: [$gcc] } ] }很多人在这一步会碰到一个跟算法题无关但很恼火的报错g 不是内部或外部命令。这基本就是 PATH 没配置好重新打开一个终端确认g --version能输出版本信息即可。另外Windows 上还经常弹出Visual C Redistributable安装提示这个和 VS Code 无关是某些软件运行 MSVC 编译出来的程序时需要的运行库。如果你的代码是 g 编译的不需要它如果你用的是 MSVC 工具链编译那最好装一下最新版的 VC Redistributable。这个组件确实经常安装失败网上还有一种叫 AIO 的合集包把 2015-2022 等多个版本打包在一起比逐个安装省事很多但注意只在官方或可信来源下载。6.2 刷题时的 IO 优化与编译选项LeetCode 的题目模板不涉及命令行输入你只需要实现Solution类里的方法。但在 OJ 或笔试平台里很多题目需要自己处理输入输出。如果你用cin和cout一定记得在main开头写std::ios::sync_with_stdio(false); std::cin.tie(nullptr);这两行代码的原理是切断 C 的stdio和 C 的iostream之间的同步并解开cin和cout的绑定关系让输入输出不再频繁冲刷缓冲区。实测在输入量达到几十万行时性能差可能有好几倍。另一个小事不要在同一个程序里混用scanf/printf和cin/cout。一旦用了sync_with_stdio(false)C 风格和 C 风格的流各自独立缓冲输出顺序可能错乱。这个坑在笔试调试时特别隐蔽因为数据量小的时候根本看不出来。关于编译选项本地自测时建议开-O2和-Wall。-Wall能帮你发现很多隐性问题比如变量未使用、比较时符号性不匹配等。刷题状态下通常不需要-g调试信息但如果你用 GDB 打断点还是加上比较好。6.3 面试作答顺序与语言特性的交叉考点面试官问股票系列时大概率不是让你直接默写 188 题而是从 121 或 122 切入再逐步加约束。我建议的回答顺序是先说清楚交易的定义一次买入 一次卖出算一笔完整交易。从 121 题开始用历史最低价做一次遍历如果面试官追问再推出状态机模型。把状态机模型统一成cash和hold两个变量然后根据不同约束扩展维度。最后讨论空间优化和时间复杂度。C 本身的语言特性也会顺带被考察。比如面试官可能会问std::vector的底层原理或者你为什么用std::max而不是手写三目运算以及 lambda 捕获、std::array和原生数组的区别。这些内容网上常被总结成八股但其实都挺实用vector的扩容机制影响你预估内存峰值lambda 的捕获方式影响std::accumulate等算法的可读性。我个人还有一个小建议练习这些 DP 题时尽量不要再写魔鬼缩进和复用变量名比如把dp、temp、res混着用。刷题时追求简洁没错但到了手写白板或在线共享文档面试时变量名本身就是一种沟通工具。像cash和hold这类有明确语义的名字会让面试官更容易跟住你的思路。这个系列刷完之后我再去看其他状态机 DP 题比如打家劫舍变体、买卖股票最优持仓明显感觉建模速度上来了。说到底股票问题就是一个维护当前状态下最优值再按约束转移的经典模型。把 121 到 714 这六道题吃透C 的实现细节和状态机 DP 的核心思想基本就都有了。最后再分享一个我自己一直在用的小技巧任何状态转移相关的题先写清楚状态定义和转移方程再动手敲代码尤其是涉及交易次数和冷冻期这种附加维度时先画一画状态之间的箭头比盯着屏幕硬写靠谱得多。