信息学奥赛NOI真题实战手把手调试‘股票买卖’DP代码讲清每个数组dpe[i]、dpb[i]的实际含义在算法竞赛中动态规划DP一直是让许多选手又爱又恨的题型。尤其是面对股票买卖这类经典问题时即使理解了状态转移方程实际编码时仍可能被各种DP数组搞得晕头转向。本文将带您以调试视角一步步拆解NOI真题中的股票买卖代码用具体数据演示dpe[i]、dpb[i]等数组如何动态变化让抽象的状态转移变得肉眼可见。1. 问题重述与核心思路假设我们有一支股票连续n天的价格记录存储在数组prices[]中。题目允许最多完成两笔交易买入和卖出各算一次操作要求计算能获得的最大利润。注意必须在再次买入前卖出之前的股票。例如给定价格序列[3,3,5,0,0,3,1,4]最优策略是第4天买入价格0第6天卖出价格3利润3第7天买入价格1第8天卖出价格4利润3 总利润为6。关键观察对于第i天我们需要考虑两个方向的状态从左到右记录到第i天为止的单次交易最大利润dpe[i]从右到左记录从第i天开始往后的单次交易最大利润dpb[i]最终答案是max(dpe[i] dpb[i1])对所有i的可能取值。2. DP数组定义与初始化让我们先明确代码中几个核心数组的定义int dpe[MAXN]; // dpe[i]: 第0天到第i天完成一次交易的最大利润 int dpb[MAXN]; // dpb[i]: 第i天到第n-1天完成一次交易的最大利润 int de[MAXN]; // de[i]: 第0天到第i天的最低买入价 int db[MAXN]; // db[i]: 第i天到第n-1天的最高卖出价初始化时需要注意边界条件de[0] prices[0]; // 第0天的最低买入价就是当天的价格 for (int i 1; i n; i) { de[i] min(de[i-1], prices[i]); dpe[i] max(dpe[i-1], prices[i] - de[i]); } db[n-1] prices[n-1]; // 最后一天的最高卖出价就是当天的价格 for (int i n-2; i 0; i--) { db[i] max(db[i1], prices[i]); dpb[i] max(dpb[i1], db[i] - prices[i]); }3. 分步调试演示让我们用具体数据[3,3,5,0,0,3,1,4]来观察这些数组的变化过程。3.1 从左到右扫描计算dpe和de天数(i)prices[i]de[i]dpe[i]解释0330初始状态无法卖出1330价格未低于之前最低价2532当前利润5-323002更新最低价但利润未超过之前4002同上5303当前利润3-03更新最大值6103利润1-01不更新7404当前利润4-04更新最大值3.2 从右到左扫描计算dpb和db天数(i)prices[i]db[i]dpb[i]解释7440最后一天无法买入6143最大卖出价4利润4-135341利润4-31小于之前最大值4044利润4-04更新最大值3044同上2550当前最高价变为5但之后无法获得正利润1352利润5-320352同上4. 合并结果与验证现在我们将dpe和dpb数组合并寻找最大两笔交易利润和分割点idpe[i]dpb[i1]总和0044104422463246423553366303从表中可见最大总和为6对应两种分割方式在第2天分割前段利润2第0-2天后段利润4第3-7天在第5天分割前段利润3第0-5天后段利润3第6-7天这与我们手动计算的最优策略一致。5. 常见错误与调试技巧在实际编码中选手常会遇到以下问题边界条件处理不当忘记初始化de[0]和db[n-1]循环范围错误如从1开始却写成从0开始状态转移理解错误// 错误写法 dpe[i] prices[i] - de[i]; // 忘记与前一天比较 // 正确写法 dpe[i] max(dpe[i-1], prices[i] - de[i]);数组大小不足题目中n的最大值通常是1e5级别需要确保数组足够大建议使用vector或全局数组MAXN1e510调试建议对于小样例可以打印出所有DP数组的值进行验证使用assert检查不变量例如assert(dpe[i] dpe[i-1]); // dpe应该单调不减 assert(dpb[i] dpb[i1]); // dpb应该单调不增6. 算法优化与变种虽然这个O(n)的解法已经足够高效但我们可以进一步优化空间复杂度int maxProfit(vectorint prices) { int n prices.size(); if (n 0) return 0; int min_price prices[0]; vectorint dpe(n, 0); for (int i 1; i n; i) { min_price min(min_price, prices[i]); dpe[i] max(dpe[i-1], prices[i] - min_price); } int max_price prices[n-1]; vectorint dpb(n, 0); for (int i n-2; i 0; i--) { max_price max(max_price, prices[i]); dpb[i] max(dpb[i1], max_price - prices[i]); } int res 0; for (int i 0; i n; i) { res max(res, dpe[i] (i1 n ? dpb[i1] : 0)); } return res; }变种问题思考如果允许完成k笔交易而非2笔如果每次交易有手续费如果交易有冷却期卖出后必须等待一天才能再买入这些变种都可以通过扩展DP状态的定义来解决核心思路仍然是清晰地定义每个状态的实际含义。