简介本资源是面向《算法导论》课程学习者与期末备考学生的实践型项目包聚焦股票买卖最佳时期这一经典动态规划问题族系统实现含单次、多次、含手续费、含冷冻期等变体的最优解法并重点应用wqs二分优化交易次数约束场景。压缩包共7个文件包含1份详尽PDF作业报告含问题建模、算法推导与复杂度分析、1个核心C实现源码每行注释清晰支持空间优化版本、2份测试数据data.txt与data2.txt、2份Markdown说明文档含项目结构与运行指引及1份LICENSE协议文件整体体积仅679KB轻量易部署。已有271人下载学习适合算法初学者理解动态规划状态设计与优化技巧也便于进阶者对比wqs二分与传统DP在约束条件下的适用边界。1. 为什么股票买卖最佳时期问题不是“找最大差值”那么简单很多同学拿到算法导论期末大作业第一反应是不就是遍历一遍数组记录最低价、算后续最大利润——这只能解 LeetCode #121最多买卖一次而本项目覆盖的是带交易次数限制、可无限次、含冷冻期、含手续费、甚至带 k 次交易成本约束的完整系列问题。真正卡住高分的关键在于理解「状态维度爆炸」如何被动态规划压缩以及当 k 变成变量比如 k1000时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 次交易且持有股票的最大利润 vectorvectorvectorlong long dp(n, vectorvectorlong long(k1, vectorlong long(2, 0)));提示使用long long是为避免大额股价如 1e9乘以天数1e5导致 int 溢出初始状态dp[0][0][1] -prices[0]第 0 天买入其余dp[0][j][0] 0dp[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)。当 n1e5, k1e3 时内存占用超 800MB无法通过评测。因此项目采用滚动数组优化只保留dp[j][0]和dp[j][1]两维// 初始化dp[j][0] 0, dp[j][1] -prices[0]对所有 j vectorvectorlong long dp(k1, vectorlong long(2, 0)); for (int j 0; j k; j) { dp[j][1] -prices[0]; } // 从第 1 天开始迭代i1 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]); } // j0 的情况单独处理不允许任何交易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则在卖出时扣减 feedp[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]303确认状态流转正确性。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 实现// 使用 pairlong long, int 表示 (利润, 交易次数) pairlong long, int dp0 {0, 0}, dp1 {-prices[0], 0}; for (int i 1; i n; i) { pairlong long, int new_dp0 max(dp0, make_pair(dp1.first prices[i] - lambda, dp1.second 1) ); pairlong long, int new_dp1 max(dp1, make_pair(dp0.first - prices[i], dp0.second) ); dp0 new_dp0; dp1 new_dp1; }max比较规则优先比 profitprofit 相同时比 cnt但实际中 profit 更大已隐含更优cnt 仅用于校验。3.3 二分搜索 λ 的边界设定与收敛判定λ 的取值范围由股价极差决定。理论下界 λ_min 0无惩罚上界 λ_max max_price此时任何交易都亏cnt0。项目采用标准二分框架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包含一组 k5000 的大数据运行wqs_binary_search.cpp与dp_k_times.cpp对比前者耗时 0.1s后者 10s性能差异达百倍。这是算法导论中「问题结构洞察优于暴力优化」的典型例证。4. 源码工程化实践从单文件调试到多用例批量验证4.1 项目目录结构与编译脚本设计源码包采用扁平化结构但通过命名规范体现模块职责dp_basic.cpp最多买卖一次#121dp_unlimited.cpp无限次交易#122dp_k_times.cpp最多 k 次#188dp_cooldown.cpp含冷冻期#309dp_fee.cpp含手续费#714wqs_binary_search.cppwqs 二分优化#188 进阶项目根目录提供Makefile支持一键编译全部CXX g CXXFLAGS -stdc17 -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.txt4.2 多用例自动化验证与结果比对为确保各实现逻辑一致项目提供verify_all.sh脚本对同一输入文件运行所有算法并比对输出#!/bin/bash INPUT_FILEdata.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_timesk2输出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、profitif (trace) { printf(lambda%lld, cnt%d, profit%lld\n, lambda, cnt, profit); }这种轻量级日志比 IDE 单步更高效尤其适合分析cnt在二分过程中如何跳变。例如当k3时若lambda5得cnt5lambda6得cnt2说明凸函数在此区间陡峭需在 [5,6] 间插值而非整数二分——但本项目数据保证整数解存在故无需处理。5. 高分作业交付技巧PDF 报告结构与答辩话术设计5.1 《股票买卖最佳时期问题.pdf》的核心内容组织该报告不是代码说明书而是按「问题抽象→模型构建→算法选择→复杂度分析→实验验证」五段式展开问题抽象用数学语言重述题目明确输入price array、输出max profit、约束k, cooldown, fee模型构建手绘状态机图如冷冻期的三个状态圆圈及带标签箭头标注转移条件算法选择对比 DP 与贪心为何贪心不适用于冷冻期因局部最优不全局最优解释 wqs 二分适用前提凸性证明f(k1)−f(k) ≥ f(k2)−f(k1)复杂度分析表格对比各算法时空复杂度突出 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 临场答辩高频问题预判与应答要点问题应答要点关联代码位置「wqs 二分中 λ 的物理意义是什么」λ 是每次交易的「影子价格」代表为获得一次额外交易权所愿支付的最高成本。它将硬约束 k 转化为软约束通过调整 λ 控制交易频次。wqs_binary_search.cpp第 45 行prices[i] - lambda「DP 状态中为什么用 long long 而不用 int」股价最大 1e9天数 1e5利润可能达 1e14int 最大约 2e9必溢出。这是工程实践中数据类型选择的典型教训。所有.cpp文件dp数组声明处「如果 k n/2是否还能用 wqs」可以但此时 k 实际无约束因最多 n/2 次有效交易应退化为无限次交易解法时间复杂度 O(n)。项目在main()中加入if (k n/2) return solve_unlimited(prices);优化。dp_k_times.cpp第 88 行最后将股票买卖最佳时期问题.pdf与src/目录打包为submission.zip命名格式学号_姓名_算法导论大作业.zip即可提交。记住高分不来自炫技而来自对每个状态转移的透彻理解以及用代码将理论具象化的执行力。本文还有配套的精品资源点击获取