第六章 动态规划——如何管理子问题依赖
开篇：三个"看似简单"的问题
问题 1：Fibonacci 数列
看起来简单："不就是递归吗？"
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)小明在面试时自信地写下这个代码。面试官说："算 fib(50) 看看。"
程序运行了 10 分钟还没出结果。
困惑：同样的逻辑，为什么 fib(20) 一秒完成，fib(50) 却要几分钟？
问题 2：钢条切割
某钢材公司需要切割不同长度的钢条出售。给定价格表：
| 长度（英寸） | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 价格（美元） | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
一根 4 英寸钢条的最优切割方式是什么？
小明用递归尝试所有切割方案：
def cut_rod(price, n):
if n == 0:
return 0
max_val = -infinity
for i in range(1, n+1):
max_val = max(max_val, price[i] + cut_rod(price, n-i))
return max_val问题：一根 10 英寸的钢条，程序跑了 5 秒。一根 30 英寸的，程序跑了 10 分钟。
困惑：为什么长度增加，时间爆炸式增长？
问题 3：最长公共子序列
给定两个字符串 "ABCDGH" 和 "AEDFHR"，找出最长公共子序列。
看起来简单："逐个字符比对呗。"
小明写了个递归：
def lcs(X, Y, m, n):
if m == 0 or n == 0:
return 0
if X[m-1] == Y[n-1]:
return 1 + lcs(X, Y, m-1, n-1)
else:
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))问题：长度 10 的字符串，秒算。长度 30 的字符串，几分钟。
困惑：为什么同样的问题，规模稍微增大就不可接受？
War Story：2024 年算法竞赛的"指数陷阱"
真实案例：2024 年某算法竞赛，选手 A 用递归解 Fibonacci 第 40 项。程序运行了 3 小时还没出结果。评委说："你的分治是对的，但你的子问题画出来有指数级重复..."
选手 A 的递归树（fib(5)）：
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \
fib(2) fib(1)关键观察：fib(3) 计算了 2 次，fib(2) 计算了 3 次。
选手 B 的记忆化版本：
memo = {}
def fib_memo(n):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]同样的 fib(40)，1 毫秒 完成。
效率差距：10^8 倍。
学习目标
完成本章学习后，你将能够：
- 识别子问题重叠：判断一个递归问题是否适合用 DP 优化
- 验证最优子结构：用"剪贴证明"判断 DP 是否能保证最优解
- 设计状态空间：从一维到多维，平衡维度与效率
- 实现记忆化与迭代：两种实现方式，理解各自的优劣
- 连接 LLM 推理：理解 KV-Cache 与 DP 记忆化的同构性
关键洞察：动态规划的核心不是"递推公式"，而是发现问题结构——子问题重叠和最优子结构需要人的判断，机器做不了。
核心叙事：DP 记忆化 ↔ KV-Cache 同构
一个令人惊讶的发现
2026 年，研究者发现：大语言模型（LLM）推理时的 KV-Cache，与动态规划的记忆化本质相同。
| DP 概念 | LLM 对应 | 共同条件 |
|---|---|---|
| 记忆化 | KV-Cache | 子问题重叠 → prefix reuse |
| 子问题图 | Token DAG | 依赖关系 DAG |
| 最优子结构 | Markov 假设 | 状态最优不依赖路径历史 |
| 状态设计 | Prompt 设计 | 影响推理效率 |
这不是类比，而是同构——同一计算思想的不同实例化。
为什么这个对应关系重要？
- 理解 DP → 理解 KV-Cache 设计决策：为什么某些 prompt 更适合缓存？
- 诊断 LLM 效率问题：推理慢 → 检查 prefix reuse 率
- 迁移优化技术：DP 的状态压缩 → KV-Cache 的 quantization
章节结构
本章遵循认知规律：
问题情境 → 直观思路 → 规范定义 → 算法实现 → 正确性分析 → 复杂度分析 → 变式练习各节要点
6.1 子问题与重叠（~500 行）
- 问题情境：Fibonacci 的指数陷阱——同一子问题被计算多次
- 直观思路：画递归树，发现重复节点
- 核心内容：子问题图、记忆化、自底向上
- 关键代码：三种 Fibonacci 实现
- 思考题：为什么 quicksort 不能用 DP 优化？
6.2 最优子结构（~450 行）
- 问题情境：最长路径的失败——剪贴证明揭示答案
- 直观思路：为什么最短路可以用 DP，最长路径不行？
- 核心内容：剪贴证明、反例构造
- 关键代码：最短路径的 DP 递推
- 思考题：0-1 背包 vs 分数背包，哪个有最优子结构？
6.3 状态设计（~500 行）
- 问题情境：状态爆炸——5 维数组导致内存不足
- 直观思路：状态 = 参数的有效组合
- 核心内容：一维到多维、空间优化
- 关键代码：LCS、编辑距离、矩阵链乘
- 思考题：如何压缩状态空间？
6.4 经典模型（~600 行）
- 问题情境：面试现场的编辑距离优化
- 直观思路：一个框架解决一族问题
- 核心内容：钢条切割、矩阵链乘、编辑距离、最优 BST
- 关键代码：Skiena 的可插拔框架
- 思考题：Knuth 优化的条件是什么？
6.5 LLM 与 DP 同构性（~400 行）
- 问题情境：KV-Cache 的记忆化重生
- 直观思路：DP 记忆化 → KV-Cache 设计
- 核心内容：四对映射、推理效率优化
- 关键代码：推理缓存策略
- 思考题：如何识别 prefix reuse？
综合练习（~350 行）
- 问题情境与直觉建立（5 题）
- 方法应用与实现（5 题）
- 错误诊断与反例（5 题）
- 方案比较与权衡（5 题）
- 变式与边界条件（5 题）
- 开放设计（5 题）
- 综合应用（5 题）
- 思考题（5 题）
- LLM 协同实验（5 题）
阅读路径建议
路径一：循序渐进（推荐）
6.1 → 6.2 → 6.3 → 6.4 → 6.5 → 练习适合：希望系统掌握动态规划的读者
路径二：LLM 导向
6.5 → 遇到概念回查前置章节 → 练习适合：主要关注 LLM 推理优化的读者
路径三：快速入门
6.1（子问题重叠） → 6.2（最优子结构） → 练习适合：希望快速建立核心概念的读者
关键概念预告
三个"为什么"
为什么 Fibonacci 递归这么慢？
- 不是因为递归本身，而是因为子问题重叠——同一子问题被计算多次
- 记忆化后：O(φ^n) → O(n)
为什么最长路径不能用 DP？
- 因为没有最优子结构——两条最长子路径拼接后可能不合法
- 最短路径有最优子结构：子路径最优 + 子路径最优 = 路径最优
为什么 KV-Cache 和 DP 记忆化同构？
- 条件相同：prefix reuse = 子问题重叠
- 有效模式识别需要人的判断
三个"如何"
如何验证最优子结构？
- 剪贴证明：假设子解非最优 → 替换 → 矛盾
- 构造反例：找两个最优子解拼接后不合法
如何设计状态？
- 子问题图视角：状态 = 子问题，边 = 依赖
- 反拓扑序求值 → 自底向上实现
如何迁移 DP 思维到 LLM？
- 状态空间设计 → KV-Cache 管理
- 子问题重叠识别 → prefix reuse 检测
- 最优子结构验证 → LLM 输出评判
写作风格说明
本章遵循教材设计哲学的七大特征：
- 问题驱动：先让学生感受到"为什么需要"，再给出定义
- 展示推理过程：从朴素方案到优化方案的演化，包括错误尝试
- 直觉先于形式：先描述直觉图景，再形式化
- 解释难点：回答"为什么这样定义""这个方法是怎么想到的"
- 例子多样化：入门例子、反例、变式、综合应用
- 练习多样化：不只是三层，包括错误诊断、方案比较、开放设计
- 终极目标：让读者面对新题时知道从哪里开始想
写在前面：动态规划最难的不是"记住递推公式"，而是识别问题结构——哪些问题适合用 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.