股票买卖动态规划全系列：从基础DP到wqs二分优化

简介：本资源是面向《算法导论》课程学习者与期末备考学生的实践型项目包，聚焦股票买卖最佳时期这一经典动态规划问题族，系统实现含单次、多次、含手续费、含冷冻期等变体的最优解法，并重点应用wqs二分优化交易次数约束场景。压缩包共7个文件，包含1份详尽PDF作业报告（含问题建模、算法推导与复杂度分析）、1个核心C++实现源码（每行注释清晰，支持空间优化版本）、2份测试数据（data.txt与data2.txt）、2份Markdown说明文档（含项目结构与运行指引）及1份LICENSE协议文件，整体体积仅679KB，轻量易部署。已有271人下载学习，适合算法初学者理解动态规划状态设计与优化技巧，也便于进阶者对比wqs二分与传统DP在约束条件下的适用边界。

1. 为什么股票买卖最佳时期问题不是“找最大差值”那么简单？

很多同学拿到算法导论期末大作业第一反应是：不就是遍历一遍数组，记录最低价、算后续最大利润？——这只能解 LeetCode #121（最多买卖一次），而本项目覆盖的是带交易次数限制、可无限次、含冷冻期、含手续费、甚至带 k 次交易成本约束的完整系列问题。真正卡住高分的关键，在于理解「状态维度爆炸」如何被动态规划压缩，以及当 k 变成变量（比如 k=1000）时，O(nk) 时间直接超时，必须切换到 wqs 二分（也称凸包优化/斜率优化）这一进阶范式。本源码包不是简单实现，而是以《算法导论》第 15 章动态规划思想为骨架，用 C++ 实现了从基础 DP 到空间优化、再到 wqs 二分的完整演进链路。每份.cpp文件对应一个子问题变体，data.txt和data2.txt提供多组边界测试用例（含全升序、全降序、单日波动、长周期震荡），配合股票买卖最佳时期问题.pdf中的数学推导与状态转移图，能帮你把「为什么状态要设成 dp[i][j][0/1]」、「为什么冷冻期要多开一维」、「wqs 二分中 λ 如何影响交易次数」这些抽象概念，变成可调试、可打印、可单步验证的代码实体。适合正在啃《算法导论》第 15 章、准备期末答辩、或想补足动态规划工程落地能力的中高阶学习者。

2. 动态规划建模：从二维状态到滚动数组的空间压缩实战

2.1 问题分类与状态定义的底层逻辑

股票买卖系列问题本质是带约束的序列决策问题。约束类型决定状态维度：

• 无限制交易（LeetCode #122）：只需记录「当前持有/未持有」两种状态，因为每次卖出后可立即买入，历史无关；
• 最多 k 次交易（LeetCode #188）：必须引入交易次数 j ∈ [0, k] 作为状态维度，因第 j 次买入依赖前 j−1 次是否完成；
• 含冷冻期（LeetCode #309）：需区分「刚卖出」「冷冻中」「可交易」三种状态，冷冻期本质是强制增加一个中间状态；
• 含手续费（LeetCode #714）：手续费在买入或卖出时扣除，影响状态转移中的利润计算，但不新增状态维度。

本项目src/目录下dp_k_times.cpp对应最多 k 次交易问题。其原始状态定义为：

// dp[i][j][0] 表示第 i 天结束时，已完成 j 次交易，且不持有股票的最大利润 // dp[i][j][1] 表示第 i 天结束时，已完成 j 次交易，且持有股票的最大利润 vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(k+1, vector<long long>(2, 0)));

提示：使用long long是为避免大额股价（如 1e9）乘以天数（1e5）导致 int 溢出；初始状态dp[0][0][1] = -prices[0]（第 0 天买入），其余dp[0][j][0] = 0，dp[0][j][1] = -prices[0]（j≥1 时首次买入仍为 -prices[0]）。

2.2 状态转移方程的物理意义与代码实现

以dp_k_times.cpp为例，核心转移逻辑如下：

// 第 i 天不持有股票（状态 0）：要么昨天就不持有，要么今天卖出 dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]); // 第 i 天持有股票（状态 1）：要么昨天就持有，要么今天买入（此时交易次数 j 必须由 j-1 升级而来） 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-1而写成dp[i-1][j][0]，则允许同一天多次买卖，逻辑错误。

该实现时间复杂度 O(nk)，空间复杂度 O(nk)。当 n=1e5, k=1e3 时，内存占用超 800MB，无法通过评测。因此项目采用滚动数组优化，只保留dp[j][0]和dp[j][1]两维：

// 初始化：dp[j][0] = 0, dp[j][1] = -prices[0]（对所有 j） vector<vector<long long>> dp(k+1, vector<long long>(2, 0)); for (int j = 0; j <= k; j++) { dp[j][1] = -prices[0]; } // 从第 1 天开始迭代（i=1） for (int i = 1; i < n; i++) { // 必须倒序更新 j，避免 dp[j-1] 被提前覆盖 for (int j = k; j >= 1; j--) { long long prev_0 = dp[j][0]; // 保存旧值用于 dp[j][1] 计算 dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]); dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i]); } // j=0 的情况单独处理（不允许任何交易，dp[0][1] 始终为 -prices[0]，dp[0][0] 始终为 0） dp[0][1] = max(dp[0][1], -prices[i]); // 允许在第 i 天买入但永不卖出（实际无意义，但保持状态一致） }

注意：内层循环j必须倒序（从 k 到 1），因为dp[j][1]依赖dp[j-1][0]，若正序更新，dp[j-1][0]已被当天新值覆盖，导致错误复用。这是滚动数组优化中最易踩的坑。

2.3 冷冻期与手续费问题的 DP 变体实现

dp_cooldown.cpp引入第三种状态dp[i][2]表示「第 i 天处于冷冻期」（即昨天刚卖出）：

// 状态定义： // dp[i][0]: 不持有，且不在冷冻期 → 可买入 // dp[i][1]: 持有股票 → 可卖出 // dp[i][2]: 刚卖出，处于冷冻期 → 下一天不可买入 // 转移： dp[i][0] = max(dp[i-1][0], dp[i-1][2]); // 从非冷冻不持或冷冻期结束转入 dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]); // 从持有或非冷冻不持买入转入 dp[i][2] = dp[i-1][1] + prices[i]; // 唯一来源：昨天持有，今天卖出

dp_fee.cpp则在卖出时扣减 fee：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee); // fee 在卖出时扣除 dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);

三份代码均提供print_dp_table()函数（注释已启用），可在小规模数据（如data.txt前 5 行）上运行并打印状态表，直观验证转移逻辑。例如输入[1,2,3,0,2]，观察dp_cooldown中dp[3][2]（第 3 天冷冻）是否等于dp[2][1]+prices[3]=3+0=3，确认状态流转正确性。

3. wqs 二分优化：当 k 达到 10⁵ 时如何将 O(nk) 降至 O(n log C)

3.1 为什么传统 DP 在大 k 场景下必然失效

当题目给定k = 100000，而n = 100000时，O(nk) = 10¹⁰，C++ 即使每秒 1e8 次操作也需 100 秒，远超时限。此时需观察：最大利润关于交易次数 k 的函数 f(k) 是上凸函数（concave）。即随着 k 增加，每多一次交易带来的边际利润递减。例如股价序列[1,2,3,4,5]，f(1)=4, f(2)=4, f(3)=4… 边际收益迅速归零。

wqs 二分（Weighted Queue Selection / Convex Hull Trick）正是利用此凸性，将「求 f(k)」转化为「对给定惩罚系数 λ，求无交易次数限制下，每次交易额外付出 λ 成本时的最大利润 g(λ)，并统计此时实际交易次数 cnt(λ）」。通过二分 λ，使 cnt(λ) = k，此时f(k) = g(λ) + k * λ。

3.2 wqs 二分在股票问题中的状态重定义与实现

wqs_binary_search.cpp将原问题重构为：每完成一次买卖，额外支付 λ 成本。此时状态定义简化为二维：

// dp[i][0]: 第 i 天不持有股票的最大利润（含已付 λ 成本） // dp[i][1]: 第 i 天持有股票的最大利润 long long dp0 = 0, dp1 = -prices[0]; // 滚动数组，仅需两个变量 for (int i = 1; i < n; i++) { long long new_dp0 = max(dp0, dp1 + prices[i] - lambda); // 卖出时扣 λ long long new_dp1 = max(dp1, dp0 - prices[i]); dp0 = new_dp0; dp1 = new_dp1; }

关键变化：prices[i] - lambda体现每次卖出的隐性成本。此时需在 DP 过程中统计实际交易次数。项目采用「路径回溯法」：在状态转移时，若dp0由dp1 + prices[i] - lambda更新，则计数器cnt++。但更高效的做法是修改状态为三元组(profit, cnt)，用 pair 实现：

// 使用 pair<long long, int> 表示 (利润, 交易次数) pair<long long, int> dp0 = {0, 0}, dp1 = {-prices[0], 0}; for (int i = 1; i < n; i++) { pair<long long, int> new_dp0 = max(dp0, make_pair(dp1.first + prices[i] - lambda, dp1.second + 1) ); pair<long long, int> new_dp1 = max(dp1, make_pair(dp0.first - prices[i], dp0.second) ); dp0 = new_dp0; dp1 = new_dp1; }

max比较规则：优先比 profit，profit 相同时比 cnt（但实际中 profit 更大已隐含更优，cnt 仅用于校验）。

3.3 二分搜索 λ 的边界设定与收敛判定

λ 的取值范围由股价极差决定。理论下界 λ_min = 0（无惩罚），上界 λ_max = max_price（此时任何交易都亏，cnt=0）。项目采用标准二分框架：

long long lambda_left = 0, lambda_right = 1e9; long long best_profit = 0, best_cnt = 0; while (lambda_left <= lambda_right) { long long mid = (lambda_left + lambda_right) / 2; auto [profit, cnt] = solve_with_lambda(prices, mid); if (cnt >= k) { // 实际交易次数过多，需提高 λ 抑制交易 best_profit = profit + k * mid; // 还原真实利润 best_cnt = cnt; lambda_left = mid + 1; } else { lambda_right = mid - 1; } }

注意：solve_with_lambda返回的profit是扣除了cnt * mid的净利，因此真实利润需profit + k * mid。当cnt > k时，说明 λ 偏小，需增大；当cnt < k时，λ 过大，需减小。由于 f(k) 是上凸函数，二分能精确命中cnt = k或最接近的点。

本项目data2.txt包含一组 k=5000 的大数据，运行wqs_binary_search.cpp与dp_k_times.cpp对比：前者耗时 < 0.1s，后者 > 10s，性能差异达百倍。这是算法导论中「问题结构洞察优于暴力优化」的典型例证。

4. 源码工程化实践：从单文件调试到多用例批量验证

4.1 项目目录结构与编译脚本设计

源码包采用扁平化结构，但通过命名规范体现模块职责：

• dp_basic.cpp：最多买卖一次（#121）
• dp_unlimited.cpp：无限次交易（#122）
• dp_k_times.cpp：最多 k 次（#188）
• dp_cooldown.cpp：含冷冻期（#309）
• dp_fee.cpp：含手续费（#714）
• wqs_binary_search.cpp：wqs 二分优化（#188 进阶）

项目根目录提供Makefile，支持一键编译全部：

CXX = g++ CXXFLAGS = -std=c++17 -O2 -Wall TARGETS = dp_basic dp_unlimited dp_k_times dp_cooldown dp_fee wqs_binary_search all: $(TARGETS) %: %.cpp $(CXX) $(CXXFLAGS) $< -o $@ clean: rm -f $(TARGETS) *.o

执行make后生成 6 个可执行文件。每个文件均内置read_input()函数，自动读取data.txt（默认）或命令行指定文件：

./dp_k_times # 读 data.txt ./dp_k_times data2.txt # 读 data2.txt

4.2 多用例自动化验证与结果比对

为确保各实现逻辑一致，项目提供verify_all.sh脚本，对同一输入文件运行所有算法并比对输出：

#!/bin/bash INPUT_FILE="data.txt" echo "=== 验证 $INPUT_FILE ===" REF=$(./dp_basic $INPUT_FILE) # 以基础版为基准 for prog in dp_unlimited dp_k_times dp_cooldown dp_fee wqs_binary_search; do OUT=$($prog $INPUT_FILE 2>/dev/null) if [ "$OUT" = "$REF" ]; then echo "✓ $prog: $OUT" else echo "✗ $prog: expected $REF, got $OUT" fi done

运行该脚本可快速定位实现偏差。例如若dp_cooldown在[1,2,3,0,2]上输出3（正确），而dp_k_times（k=2）输出4，则说明后者未正确处理冷冻期约束，需检查状态定义。

4.3 关键调试技巧：状态打印与断点注入

所有.cpp文件在main()开头预留调试开关：

bool DEBUG = false; if (argc > 2 && string(argv[2]) == "--debug") DEBUG = true; if (DEBUG) { cout << "Prices: "; for (int x : prices) cout << x << " "; cout << "\n"; }

启用后（./dp_k_times data.txt --debug），程序会打印输入序列及每轮 DP 的关键状态。对于 wqs 二分，还可添加--trace参数输出每次二分的lambda、cnt、profit：

if (trace) { printf("lambda=%lld, cnt=%d, profit=%lld\n", lambda, cnt, profit); }

这种轻量级日志比 IDE 单步更高效，尤其适合分析cnt在二分过程中如何跳变。例如当k=3时，若lambda=5得cnt=5，lambda=6得cnt=2，说明凸函数在此区间陡峭，需在 [5,6] 间插值而非整数二分——但本项目数据保证整数解存在，故无需处理。

5. 高分作业交付技巧：PDF 报告结构与答辩话术设计

5.1 《股票买卖最佳时期问题.pdf》的核心内容组织

该报告不是代码说明书，而是按「问题抽象→模型构建→算法选择→复杂度分析→实验验证」五段式展开：

• 问题抽象：用数学语言重述题目，明确输入（price array）、输出（max profit）、约束（k, cooldown, fee）；
• 模型构建：手绘状态机图（如冷冻期的三个状态圆圈及带标签箭头），标注转移条件；
• 算法选择：对比 DP 与贪心（为何贪心不适用于冷冻期？因局部最优不全局最优）；解释 wqs 二分适用前提（凸性证明：f(k+1)−f(k) ≥ f(k+2)−f(k+1)）；
• 复杂度分析：表格对比各算法时空复杂度，突出 wqs 二分将时间从 O(nk) 降至 O(n log C)；
• 实验验证：用data.txt和data2.txt的运行时间与结果截图，证明优化有效性。

提示：答辩时不要背诵 PDF，而是用「问题驱动」话术。例如被问「为什么用 wqs 二分？」，回答：「当 k 达到 1e5，传统 DP 内存和时间双爆，我观察到利润函数具有凸性，于是用 wqs 二分将约束优化转化为无约束优化，这是《算法导论》第 16 章贪心策略的延伸应用。」

5.2 源码注释规范与可读性增强

项目所有.cpp文件遵循统一注释规范：

• 文件头注明对应 LeetCode 编号、时间/空间复杂度、核心思想；
• 每个函数前用/** */描述功能、参数、返回值；
• 关键状态转移行右侧添加// 买入：消耗一次交易配额，从 j-1 状态转移类注释；
• 所有变量名直白（min_price,max_profit_with_cooldown），禁用a,b,tmp。

例如dp_k_times.cpp中空间优化部分：

// 滚动数组优化：dp[j][0] 表示完成 j 次交易后不持股的最大利润 // 注意：j 必须倒序更新，否则 dp[j-1][0] 会被提前覆盖 for (int j = k; j >= 1; j--) { dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]); // 继续不持 or 卖出 dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i]); // 继续持有 or 买入（触发第 j 次） }

这种注释让 TA 一眼看懂设计意图，而非猜测代码行为。

5.3 临场答辩高频问题预判与应答要点

最后，将股票买卖最佳时期问题.pdf与src/目录打包为submission.zip，命名格式学号_姓名_算法导论大作业.zip，即可提交。记住：高分不来自炫技，而来自对每个状态转移的透彻理解，以及用代码将理论具象化的执行力。

本文还有配套的精品资源，点击获取