第六章 综合练习
设计原则
本章练习遵循教材设计哲学（参考 Ch1/Ch2/Ch5）：
- 问题驱动：不只是"计算复杂度"，而是"为什么这样设计"
- 展示推理：不只给答案，还要展示思考过程
- 多样化：包括反例、变式、边界条件、开放设计
- 无固定三层：避免机械模仿，推动真正的理解
一、问题情境与直觉建立
1. 为什么 Fibonacci 递归这么慢？
用具体例子说明：fib(5) 的调用树，哪些节点被重复计算？
2. 最优子结构的直觉
为什么最短路径有最优子结构，最长简单路径没有？用剪贴证明解释。
3. 状态设计的权衡
状态维度越多越好吗？分析维度与空间的权衡。
4. 可插拔框架的威力
为什么一个 DP 框架能解决一族问题？用编辑距离 vs LCS 说明。
5. KV-Cache 的本质
KV-Cache 和 DP 记忆化有什么共同条件？用 prefix reuse 解释。
二、方法应用与实现
6. Fibonacci 三阶实现
实现三种版本：
- 朴素递归：O(φ^n)
- 记忆化：O(n)
- 空间优化：O(1)
对比运行时间（n=30, 40, 50）。
7. LCS 完整实现
实现 LCS，包括：
- 基本版本：O(mn) 空间
- 滚动数组：O(n) 空间
- 路径重构：输出最长公共子序列
8. 钢条切割路径重构
实现钢条切割，输出最优切割方案（不只是收益）。
9. 矩阵链乘 Knuth 优化
对比普通版本 O(n³) 和 Knuth 优化版本 O(n²)，测试 n=100。
10. KV-Cache 模拟
模拟 KV-Cache 的 prefix reuse：
- 给定 5 个请求
- 计算缓存复用率
- 分析效率提升
三、错误诊断与反例
11. 子问题重叠误判
有人用 DP 优化 Quicksort，分析错误原因。
12. 最优子结构遗漏
最长简单路径用 DP，构造反例说明剪贴失败。
13. 状态维度错误
某问题设计了 5 维状态，空间爆炸，分析改进方案。
14. 初始化遗漏
编辑距离忘记初始化第一行/列，预测错误。
15. KV-Cache 失效场景
给定无 prefix reuse 的场景，分析 KV-Cache 失效原因。
四、方案比较与权衡
16. 记忆化 vs 迭代
对比两种 DP 实现方式：
- 适用场景
- 实现难度
- 空间/时间复杂度
17. 滚动数组 vs 状态压缩
对比两种空间优化技术：
- 适用条件
- 效果对比
- 实现难度
18. 编辑距离 vs LCS
对比两个问题的框架差异：
- 桩函数差异
- 递推式差异
- 复杂度差异
19. DP vs 贪心
对比两种策略：
- 适用条件（最优子结构 + 贪心选择性质）
- 反例构造
- 复杂度差异
20. KV-Cache vs 无缓存
对比两种推理策略：
- 条件差异
- 效率差异
- 空间权衡
五、变式与边界条件
21. Tribonacci（三阶 Fibonacci）
定义：T(n) = T(n-1) + T(n-2) + T(n-3)
设计状态，实现 DP，空间优化。
22. 带权 LCS
字符有权重，求权重之和最大的 LCS。设计状态和递推式。
23. 最长公共子串
必须是连续的，设计状态（与 LCS 不同）。
24. TSP 状态爆炸
分析 TSP 的状态空间大小（n=10, 20, 30），讨论为什么 O(n² × 2^n) 仍比暴力好。
25. Token 依赖非 DAG
如果 LLM 的 attention 是双向的（非因果），KV-Cache 策略需如何调整？
六、开放设计
26. 新问题判断
给定问题（如"汉诺塔"），判断：
- 是否有子问题重叠？
- 是否有最优子结构？
- 是否适合用 DP？
27. DP 识别器设计
设计一个 Agent：
- 输入：问题描述
- 输出：是否适合 DP + 状态设计建议
28. 桩函数创新
为"最长公共子串"设计可插拔框架的桩函数。
29. KV-Cache 管理策略
设计动态 KV-Cache 管理策略：
- 缓存哪些 token？
- 何时丢弃？
- 类比 DP 的滚动数组
30. LLM 推理优化
设计 LLM 推理优化方案：
- Prefix reuse 检测
- Batch 推理组合
- 复杂度分析
七、综合应用
31. 课程安排问题
用 DP 解决实际问题：安排课程表（避免时间冲突），设计状态。
32. 最优股票买卖
用 DP 解决：最多 k 次交易的最优收益，设计状态（三维）。
33. 排课 Agent
设计一个排课 Agent，组合 DP（小规模精确）+ 启发式（大规模近似）。
34. 真实 LCS
用 LCS 解决实际问题：基因序列比对，对比不同变体（带权、子串）。
35. 综合挑战
选择一个 NP-hard 问题（如 SAT），设计求解器：
- 小规模：DP 或回溯
- 大规模：启发式
- 分析复杂度
八、思考题
36. 为什么 DP 需要两个条件？
子问题重叠和最优子结构，为什么都是必要？缺一个会怎样？
37. 如何判断问题适合 DP？
三步判断法：
- 是否有子问题重叠？
- 是否有最优子结构？
- 状态空间是否有限？
38. 框架思维的价值？
可插拔框架为什么比单独实现更强大？迁移能力在哪？
39. DP 与 LLM 的本质连接？
为什么理解 DP 能帮助理解 KV-Cache？人的判断在哪？
40. 搜索策略的演进路径？
从贪心到 GoT：贪心 → DP → ToT → GoT。分析每一步的改进。
九、LLM 协同实验
41. 递推式生成
让 LLM 为新问题（如"书本分页"）生成 DP 递推式，你验证最优子结构。
42. 桩函数设计
让 LLM 扩展编辑距离框架支持新变体（如"最长公共子串"），你评判桩函数设计。
43. KV-Cache 策略
让 LLM 设计 KV-Cache 管理策略，你分析 prefix reuse 条件。
44. 故障诊断
给定错误的 DP 实现（状态定义错误），让 LLM 找 bug，你验证。
45. 综合挑战
用 LLM 协同解决 TSP（小规模 n≤15）：
- LLM 生成状态设计
- 你实现并验证
- 对比效率
附录：实验数据模板
Fibonacci 三版本对比
| n | 朴素递归时间 | 记忆化时间 | 空间优化时间 |
|---|---|---|---|
| 30 | |||
| 40 | |||
| 50 |
LCS 空间优化对比
| m=n | 基本版本空间 | 滚动数组空间 | 效率倍数 |
|---|---|---|---|
| 100 | |||
| 1000 | |||
| 10000 |
矩阵链乘 Knuth 优化
| n | 普通版本时间 | Knuth 优化时间 | 效率倍数 |
|---|---|---|---|
| 10 | |||
| 50 | |||
| 100 |
KV-Cache 效率分析
| 场景 | 无缓存时间 | 有缓存时间 | Prefix reuse 率 |
|---|---|---|---|
| 5 个请求，共享前缀 | |||
| 5 个请求，无共享 |
实验指导
如何记录推理收据？
每次与 LLM 协作解决 DP 问题时，记录：
- 问题描述：清晰的问题陈述
- 状态设计过程：
- LLM 建议：...
- 你的质疑：...
- 最终方案：...
- 最优子结构验证：剪贴证明过程
- 实现与测试：代码和测试结果
- 反思：
- LLM 的建议哪些正确？
- 哪些需要你修正？
- 人的判断在哪？
如何分析 Prefix Reuse 率？
给定一组 LLM 推理请求，分析：
- 统计每个请求的 token 数
- 找共享前缀（最长公共前缀）
- 计算 reuse token 数
- 计算复用率：reuse token 数 / 总 token 数
- 分析 KV-Cache 效率提升
学习目标自检
完成练习后，应能回答：
- 识别子问题重叠：给定递归问题，判断是否适合 DP 优化
- 验证最优子结构：用剪贴证明判断 DP 正确性
- 设计状态空间：从一维到多维，平衡维度与效率
- 实现记忆化与迭代：两种方式，理解优劣
- 连接 LLM 推理：理解 KV-Cache 与 DP 记忆化的同构性
写在最后：动态规划最难的不是"记住递推公式"，而是识别问题结构。练习的目标是让你面对新题时，知道从哪里开始想。
参考文献：
- Cormen T H, et al. Introduction to Algorithms[M]. 4th ed. MIT Press, 2022. Chapter 15.
- Skiena S S. The Algorithm Design Manual[M]. 3rd ed. Springer, 2020. Chapter 10.
- Kleinberg J, Tardos E. Algorithm Design[M]. Pearson, 2005. Chapter 6.
- Yao S, Yu D, Zhao J, et al. Tree of Thoughts[C]//NeurIPS. 2023.