1. 项目概述从三道股票买卖问题看动态规划的状态机建模最近在重新捡起C刷算法题正好跟着“代码随想录”的路线图一口气啃下了买卖股票系列里比较有代表性的三道题允许最多K次交易的、包含冷冻期的、以及含手续费的。这三道题可以说是动态规划中“状态机”思想的绝佳练兵场。很多朋友一看到“股票”、“动态规划”就觉得头大感觉状态定义五花八门转移方程云里雾里。其实只要你理解了背后的“状态机”模型这三道题乃至整个系列都能迎刃而解。今天我就以这三道题为例结合C的复健过程把动态规划解股票问题的核心套路掰开揉碎了讲清楚。无论你是正在准备面试还是想巩固DP思想相信这篇从实战中总结的经验都能让你对“状态”和“选择”有更深刻的理解。2. 核心思路拆解统一的状态机视角买卖股票问题的动态规划解法之所以经典是因为它完美地诠释了如何将现实中的决策过程抽象成有限状态及其之间的转移。我们不要被每道题不同的条件交易次数K、冷冻期、手续费吓到它们都是在同一个核心模型上添加的“约束”。理解了这个模型就掌握了钥匙。2.1 状态定义的精髓持有与未持有所有股票买卖问题的基石都是这两个状态持有股票和未持有股票。在任何一天结束时你只能处于这两种状态之一。这听起来简单但却是定义dp数组的关键。dp[i][0]: 表示在第i天结束时持有一支股票所能获得的最大利润。dp[i][1]: 表示在第i天结束时未持有任何股票所能获得的最大利润。这里的“持有”不一定非得是今天买的也可能是昨天或更早买的一直持有到今天。“未持有”也不一定是今天卖的可能早就卖了或者一直空仓。注意有些题解或“代码随想录”里可能会使用更细致的状态比如把“未持有”细分为“今天卖出后未持有”和“非今天卖出未持有”以处理冷冻期。但最根本的依然是“持有”和“未持有”这两个核心状态。我们先从基础理解再处理复杂情况。2.2 状态转移每一天的“选择”动态规划的魅力在于“状态转移”即今天的状态是如何从昨天的状态“转移”过来的。对应到每一天你面对股价prices[i]都有几个选择如果今天结束时想处于“持有”状态 (dp[i][0])选择一昨天就持有今天不动。利润继承自dp[i-1][0]。选择二昨天未持有今天买入。利润为dp[i-1][1] - prices[i]因为支出了prices[i]的成本。dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i])如果今天结束时想处于“未持有”状态 (dp[i][1])选择一昨天就未持有今天不动。利润继承自dp[i-1][1]。选择二昨天持有今天卖出。利润为dp[i-1][0] prices[i]因为获得了prices[i]的收入。dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i])这就是最基础的、无限次交易、无冷冻期、无手续费的股票买卖问题的状态转移方程。它像一台精密的机器清晰地刻画了每一天的决策如何影响最终的利润。2.3 引入约束K次、冷冻期与手续费上面这个“二元状态机”是母版。三道难题无非是在这个母版上增加规则188. 买卖股票的最佳时机IV (最多K次交易)交易次数有限制。一次完整的交易由“买入”和“卖出”组成。我们需要在状态中增加一个维度j来记录已经完成的交易次数这里通常将买入算作一次交易的开始。状态变为dp[i][j][0/1]表示第i天在最多进行j次交易的前提下持有/未持有股票的最大利润。转移时买入操作会消耗一次交易机会j-1。309. 买卖股票的最佳时机含冷冻期卖出后需要冷却一天才能买入。这影响了“持有”状态的转移。你不能从“昨天卖出”的状态直接转移到“今天买入”因为昨天卖出后处于冷冻期。因此需要更精细地区分“未持有”状态是处于冷冻期还是可以自由购买通常我们会引入第三个状态或者用dp[i-2]来代表冷冻期前的状态。714. 买卖股票的最佳时机含手续费每次卖出时需要支付一笔手续费。这个最简单它只影响“卖出”这个动作的收益。在“未持有”状态的转移方程中卖出所得的利润变为dp[i-1][0] prices[i] - fee。你看无论题目怎么变我们都是在调整那台“状态机”的转移规则和状态定义。抓住了这个本质解题就有了清晰的路线图。3. 核心细节解析与实操要点理解了统一模型我们深入到每道题的实现细节。我会用C代码展示并解释关键点。为了清晰我会先处理相对简单的含手续费问题再处理冷冻期最后解决最复杂的K次交易问题。这个顺序有助于我们层层递进地理解状态机的扩展。3.1 714. 买卖股票的最佳时机含手续费——状态机的微调这道题是基础模型的直接变种只多了一个卖出时的固定成本。它的状态定义和基础模型完全一致dp[i][0]: 第i天持有股票的最大利润。dp[i][1]: 第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] - fee)//卖出时扣除手续费初始化dp[0][0] -prices[0]// 第一天就买入dp[0][1] 0// 第一天什么都不做C实现要点class Solution { public: int maxProfit(vectorint prices, int fee) { int n prices.size(); if (n 2) return 0; // 使用滚动数组优化空间因为dp[i]只依赖于dp[i-1] int hold -prices[0]; // 对应dp[i][0] int notHold 0; // 对应dp[i][1] for (int i 1; i n; i) { // 保存旧状态避免本次计算被覆盖 int preHold hold; int preNotHold notHold; // 状态转移 hold max(preHold, preNotHold - prices[i]); notHold max(preNotHold, preHold prices[i] - fee); } // 最后一天未持有股票的状态才是最终最大利润 return notHold; } };实操心得这里使用了“滚动数组”进行空间优化将二维dp数组压缩为两个变量。这是动态规划常见的优化技巧能显著降低空间复杂度到O(1)。关键点在于在更新hold和notHold之前必须用临时变量保存它们前一天的值preHold,preNotHold否则更新顺序会导致状态依赖错误。这是一个非常容易踩的坑。3.2 309. 买卖股票的最佳时机含冷冻期——状态的精细化冷冻期的加入使得“未持有”状态不能再一概而论。我们需要区分“今天卖出后进入冷冻期”和“已经过了冷冻期可以自由交易”。一个清晰的方法是引入三个状态状态0: 持有股票(dp[i][0])状态1: 不持有股票且今天不处于冷冻期即可以买入(dp[i][1])状态2: 不持有股票且今天处于冷冻期即昨天刚卖出(dp[i][2])状态转移分析从状态0持有出发可以继续保持持有dp[i-1][0]可以今天卖出卖出后明天将进入冷冻期所以今天结束后进入状态2dp[i-1][0] prices[i]因此dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i])。注意只能从状态1非冷冻期买入。从状态1非冷冻期可买出发可以继续保持空仓dp[i-1][1]可以今天买入进入状态0dp[i-1][1] - prices[i]因此dp[i][1] max(dp[i-1][1], dp[i-1][2])等等这里容易错。状态1可以由昨天的状态1继续空仓和昨天的状态2冷冻期结束转移而来。dp[i][1] max(dp[i-1][1], dp[i-1][2])。从状态2冷冻期出发冷冻期只有一天今天不能做任何操作明天自动进入状态1。所以今天的状态2只可能来自昨天状态0的卖出操作。因此dp[i][2] dp[i-1][0] prices[i-1]不对这个方程下标容易乱。更准确的描述是第i天处于冷冻期意味着第i-1天卖出了股票。所以dp[i][2] dp[i-1][0] prices[i-1]。初始化dp[0][0] -prices[0]// 第一天买入dp[0][1] 0// 第一天什么都没做也不在冷冻期dp[0][2] 0// 第一天不可能处于冷冻期初始化为0或一个不影响计算的值C实现class Solution { public: int maxProfit(vectorint prices) { int n prices.size(); if (n 2) return 0; // dp[i][0]: 持有, dp[i][1]: 不持有(非冷冻), dp[i][2]: 不持有(冷冻) vectorvectorint dp(n, vectorint(3, 0)); dp[0][0] -prices[0]; for (int i 1; i n; i) { // 状态0: 今天持有 max(昨天就持有, 昨天非冷冻期今天买入) dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i]); // 状态1: 今天非冷冻期 max(昨天就非冷冻期, 昨天冷冻期结束) dp[i][1] max(dp[i-1][1], dp[i-1][2]); // 状态2: 今天冷冻期 昨天持有并卖出 dp[i][2] dp[i-1][0] prices[i]; } // 最后一天持有股票没有意义最大利润在状态1或状态2中 return max(dp[n-1][1], dp[n-1][2]); } };注意事项冷冻期问题的状态定义和转移是这三题中最需要仔细推敲的。务必画出一个状态转移图明确每个状态的含义和来源。我个人的经验是把“冷冻期”状态理解为“今天不能动”的被动状态它的值完全由前一天的“主动卖出”动作决定这样思考会更清晰。另外初始化时dp[0][2]设为0是合理的因为第一天之前没有交易自然不可能是冷冻期。3.3 188. 买卖股票的最佳时机IV——维度的扩展这是本系列最难的一题因为它增加了“交易次数”这个维度。我们需要一个三维dp数组dp[i][k][0/1]表示第i天最多进行了k次交易注意定义一次交易指买入卖出且当前持有(1)/不持有(0)股票的最大利润。状态转移方程dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i])今天不持有要么昨天就不持有要么昨天持有今天卖出。卖出操作不会开启新交易所以交易次数k不变。dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])今天持有要么昨天就持有要么昨天不持有今天买入。买入操作标志着一笔交易的开始所以要从k-1次交易的状态转移过来。初始化 这是本题最容易出错的地方。我们需要初始化第0天i0的所有k和状态。对于所有交易次数k 1dp[0][k][0] 0// 第0天不持有股票利润为0。dp[0][k][1] -prices[0]// 第0天持有股票说明进行了买入利润为-prices[0]。对于k 0dp[i][0][0] 0// 不允许交易不持有股票利润始终为0。dp[i][0][1] -INF// 不允许交易却持有股票这是一个不可能的状态用负无穷表示。一个重要的优化如果给定的最大交易次数K大于等于prices数组长度的一半n/2那么这道题就退化成了“无限次交易”的情况。因为n天里最多只能进行n/2次完整的交易买入卖出交替。此时可以直接用贪心算法求解避免三维DP的大开销。C实现class Solution { public: int maxProfit(int K, vectorint prices) { int n prices.size(); if (n 2) return 0; // 优化如果K很大相当于无限次交易 if (K n / 2) { int maxProfit 0; for (int i 1; i n; i) { if (prices[i] prices[i-1]) { maxProfit prices[i] - prices[i-1]; } } return maxProfit; } // 三维DP数组初始化为0 vectorvectorvectorint dp(n, vectorvectorint(K1, vectorint(2, 0))); // 初始化第0天 for (int k 1; k K; k) { dp[0][k][0] 0; // 第0天不持有 dp[0][k][1] -prices[0]; // 第0天持有买入 } // k0的情况dp[i][0][0]0已在定义中dp[i][0][1]用不到保持0或负无穷均可 // 状态转移 for (int i 1; i n; i) { for (int k 1; k K; k) { // 今天不持有 max(昨天不持有, 昨天持有今天卖出) dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i]); // 今天持有 max(昨天持有, 昨天不持有今天买入) 注意买入消耗一次交易机会(k-1) dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]); } } // 最终答案最后一天交易次数不超过K且不持有股票 return dp[n-1][K][0]; } };踩坑实录三维DP的空间复杂度是O(n*K)在K和n较大时可能超内存。同样可以进行空间优化因为dp[i]只依赖于dp[i-1]。我们可以只维护两个二维数组dp_k_0和dp_k_1分别表示对于各个k值当前天不持有和持有的最大利润。在更新时需要特别注意k的遍历顺序。对于dp_k_1[k]它依赖于dp_k_0[k-1]昨天的值所以如果k从小到大遍历dp_k_0[k-1]可能已经被今天的数据覆盖。安全的做法是在每一天先计算出所有k对应的新值再统一更新数组或者将k从大到小遍历。这是空间优化时一个非常经典的细节。4. 实操过程与核心环节实现理论讲完了我们来看看在具体的C编码环境中如何高效地实现和调试这类题目。我个人的复健环境是VSCode CMake GCC这套组合在Linux和Windows下都表现得很稳定。4.1 环境搭建与测试框架首先确保你的C编译环境就绪。对于算法刷题一个简单的单文件编译就够了但建立一个测试框架会事半功倍。我习惯为每道题创建一个单独的.cpp文件并在同一个项目里写一个简单的main函数来测试。// solution_714.cpp #include iostream #include vector #include algorithm using namespace std; class Solution714 { public: int maxProfit(vectorint prices, int fee) { // ... 实现代码同上 } }; // 测试用例 int main() { Solution714 sol; vectorint prices1 {1, 3, 2, 8, 4, 9}; int fee1 2; cout Test 1 (expected 8): sol.maxProfit(prices1, fee1) endl; vectorint prices2 {1, 3, 7, 5, 10, 3}; int fee2 3; cout Test 2 (expected 6): sol.maxProfit(prices2, fee2) endl; return 0; }使用CMakeLists.txt来管理编译cmake_minimum_required(VERSION 3.10) project(StockProblems) set(CMAKE_CXX_STANDARD 17) add_executable(solve_714 solution_714.cpp) add_executable(solve_309 solution_309.cpp) add_executable(solve_188 solution_188.cpp)这样你可以分别编译和运行每个问题的代码。g -stdc17 solution_714.cpp -o test_714 ./test_714是更直接的命令行方式。4.2 调试技巧打印DP表对于动态规划问题尤其是状态多的比如188题的三维DP肉眼检查逻辑错误很难。最有效的调试方法就是打印出关键的DP表。例如对于188题在状态转移循环里加入调试打印// ... 在状态转移循环内部或之后 if (i n-1) { // 打印最后一天的dp表 cout Final DP table (day i ): endl; for (int k 0; k K; k) { cout k k : (notHold dp[i][k][0] , hold dp[i][k][1] ) endl; } }通过观察最终的状态值你可以验证你的转移方程和初始化是否正确。比如dp[n-1][k][1]最后一天还持有股票的值理论上应该小于或等于dp[n-1][k][0]因为最后一天持有股票无法变现不是最优解。4.3 空间优化版本的实现以188题为例展示如何将三维DP优化为二维滚动数组int maxProfit(int K, vectorint prices) { int n prices.size(); if (n 2) return 0; if (K n / 2) return greedyMaxProfit(prices); // 贪心函数省略 // dp[k][0]: 当前天最多k次交易不持有股票的最大利润 // dp[k][1]: 当前天最多k次交易持有股票的最大利润 vectorvectorint dp(K1, vectorint(2, 0)); // 初始化第0天对于所有k1持有股票是-prices[0] for (int k 1; k K; k) { dp[k][1] -prices[0]; } // k0时dp[0][0]0, dp[0][1] -INF (用0代替因为会被max过滤掉) for (int i 1; i n; i) { // 注意k需要从大到小遍历因为dp[k][1]依赖于dp[k-1][0]旧值 for (int k K; k 1; --k) { // 更新不持有状态可以用今天的旧值也可以从昨天的持有状态卖出 dp[k][0] max(dp[k][0], dp[k][1] prices[i]); // 更新持有状态可以用今天的旧值也可以从昨天的不持有状态买入消耗一次交易 // 注意这里的dp[k-1][0]是昨天i-1天的、交易次数为k-1的不持有状态 // 由于k从大到小遍历此时的dp[k-1][0]还没有被今天的数据覆盖仍然是昨天的值 dp[k][1] max(dp[k][1], dp[k-1][0] - prices[i]); } } return dp[K][0]; }核心技巧k的从大到小遍历是空间优化的精髓。因为dp[k][1]依赖于dp[k-1][0]如果k从小到大遍历当计算dp[k][1]时dp[k-1][0]已经被更新为第i天的值了而我们需要的是第i-1天的值。从大到小遍历保证了依赖项还是“旧”数据。这个技巧在背包问题等DP优化中也非常常见。5. 常见问题与排查技巧实录在实现和调试这几道题的过程中我遇到了不少坑也总结出一些共性的问题和排查方法。5.1 问题一状态定义混淆特别是冷冻期症状代码跑出来的结果比预期小或者在某些边界用例如价格一直下跌上出错。根因对“状态”的理解不到位。比如在冷冻期问题中错误地将状态定义为“今天买入”、“今天卖出”、“今天休息”导致转移方程复杂且容易漏掉情况。排查回归最本质的“持有”和“未持有”。先写出基础二元状态转移方程。思考新增约束冷冻期如何影响这两个状态的转移。冷冻期影响的是“买入”这个动作的来源状态。你不能从“卖出后的第二天”这个状态买入。画出状态转移图。用圆圈表示状态箭头表示转移边上标注动作买入、卖出、无操作和条件/收益。这是理清思路最直观的方法。用极简用例手动模拟DP表。例如价格数组[1,2,3,4]手动计算每一天每个状态的dp值与程序输出对比。5.2 问题二初始化错误尤其是多维DP症状程序在第一个交易日或交易次数为0时就计算出错。根因没有仔细考虑第0天或基准情况所有可能状态的初始值。排查清单对于“持有”状态 (dp[...][1])第0天如果想持有必须执行买入操作所以初始利润通常是-prices[0]。对于“不持有”状态 (dp[...][0])第0天如果不持有利润为0。对于交易次数维度 (k)k0代表不允许交易。此时“持有股票”是一个非法状态应初始化为一个非常小的值如INT_MIN/2确保在max比较中不会被选中。dp[i][0][0]始终为0。k1时按上述规则初始化。对于冷冻期问题明确每个状态在第0天的含义。第0天不可能处于冷冻期状态2。5.3 问题三空间优化时的状态覆盖问题症状使用了滚动数组或变量压缩后结果与未优化的二维/三维DP版本不一致。根因状态更新顺序错误新值覆盖了旧值而后续计算又需要那个旧值。解决方案临时变量法像手续费问题代码那样在更新前用临时变量保存旧状态。反向遍历法像188题空间优化那样当今天的状态依赖于“更小”的索引如k-1的旧状态时从大到小遍历可以避免覆盖。复制数组法最稳妥但空间稍大的方法每天计算一个新的状态数组计算完毕后再替换旧的。5.4 问题四贪心与DP的边界条件处理症状在188题中当K值很大时程序运行超时或内存超限。根因没有利用“当K n/2时问题退化为无限次交易”的性质。解决务必在DP开始前判断if (K n / 2)如果成立则直接调用贪心算法计算所有上升区间的利润和。这个剪枝至关重要。5.5 一个实用的调试模板当你不确定DP哪里出错时可以把这个调试函数插入你的代码void printDP(const vectorvectorvectorint dp, int day, int maxK) { cout Day day endl; for (int k 0; k maxK; k) { printf(k%d: notHold%d, hold%d\n, k, dp[day][k][0], dp[day][k][1]); } cout endl; } // 在循环中调用 printDP(dp, i, K);对比你手动计算的前几天的DP值很快就能定位是初始化不对还是转移方程写错了。6. 总结与进阶思考通过这三道题的集中攻克我对动态规划的状态机思想有了肌肉记忆般的理解。股票问题就像一个标准的“模版”其核心是定义清楚有几种状态以及状态之间如何通过“选择”买入、卖出、持有进行转移。任何附加条件都是对这个状态机转移规则的修改。我个人最深的体会是不要一上来就想着套公式。先拿出一张纸问自己几个问题在这个问题里一天结束时我有哪几种状态持有/未持有细分对于每个状态我是怎么到达这里的昨天可能是什么状态通过什么操作变成了今天这个状态这个操作对我的利润有什么影响加价格减价格减手续费第0天这些状态初始值应该是什么把这些问题回答清楚状态转移方程自然就出来了。然后就是小心初始化注意遍历顺序特别是空间优化时最后用几个简单用例验证。这套方法不仅适用于股票问题很多其他DP问题比如打家劫舍、爬楼梯变种都可以用状态机的思维来建模。掌握了这个工具你会发现很多看似复杂的DP问题其实都是在操作一台精心设计的状态机器。