6.1 子问题与重叠——朴素递归的困境

问题情境：Fibonacci 的"指数陷阱"

面试现场的尴尬

小明在面试时自信满满。面试官问："实现 Fibonacci 数列。"

小明写下了经典的递归：

python

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

面试官点点头："算 fib(20) 看看。"

程序瞬间返回结果：6765。

面试官继续："算 fib(50) 看看。"

程序开始运行……10 秒后还没出结果。面试官看了看表，说："为什么 fib(20) 一秒完成，fib(50) 却这么慢？同样的逻辑啊。"

小明愣住了："确实……同样的逻辑……为什么差距这么大？"

第一次困惑：规模增长 vs 时间增长

小明回家后做了个实验：

n	fib(n) 值	运行时间
10	55	<0.1 秒
20	6765	<0.1 秒
30	832040	~1 秒
40	102334155	~10 秒
50	12586269025	>1 分钟

关键观察：n 每增加 10，时间大约增加 10 倍。

这不是线性的增长（那应该每增加 10，时间增加 10），而是指数增长。

小明困惑了："为什么同样的递归逻辑，规模增加一点点，时间就爆炸式增长？"

第二次困惑：不是"递归慢"，而是"重复计算"

小明有个直觉：递归本身不慢——归并排序也是递归，但时间复杂度是 O(n log n)，很高效。

他画了个图：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 次
fib(1) 被调用了 5 次

这不是"递归慢"，而是同一个子问题被计算了多次！

小明恍然大悟："不是规模增加导致时间爆炸，而是重复计算导致时间爆炸！"

直观思路：把重复的部分"记住"

第一次改进：引入"备忘录"

小明想：既然 fib(3) 被计算了两次，为什么不"记住"第一次的结果，第二次直接用？

python

memo = {}  # 备忘录
def fib_memo(n):
    if n in memo:  # 如果已经算过，直接返回
        return memo[n]
    if n <= 1:
        result = n
    else:
        result = fib_memo(n-1) + fib_memo(n-2)
    memo[n] = result  # 记住结果
    return result

测试：

n	fib(n) 值	运行时间
50	12586269025	<0.001 秒

效率提升：从 >1 分钟 → <1 毫秒。10^6 倍提升。

关键洞察：不是优化了递归本身，而是避免了重复计算。

第二次改进：不用递归，直接填表

小明继续思考：既然每个 fib(i) 只需要算一次，为什么不直接按顺序计算？

python

def fib_iter(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

测试：同样的 fib(50)，<0.001 秒。

关键区别：

记忆化（自顶向下）：先调用 fib(50)，发现需要 fib(49) 和 fib(48)，再调用它们……
迭代（自底向上）：先算 fib(2)，再算 fib(3)，……最后算 fib(50)

直觉：迭代更像"填表"——按顺序填写，每个格子只填一次。

第三次改进：还能更省空间吗？

小明发现：计算 fib(50) 时，dp 表有 51 个格子，但每次计算只需要前两个格子（dp[i-1] 和 dp[i-2]）。

能不能只保留前两个格子？

python

def fib_optimized(n):
    if n <= 1:
        return n
    prev = 0
    curr = 1
    for i in range(2, n + 1):
        next = prev + curr
        prev = curr
        curr = next
    return curr

测试：同样的 fib(50)，<0.001 秒，但内存从 O(n) → O(1)。

规范定义：子问题重叠与记忆化

什么是子问题？

定义：在递归求解过程中，每个递归调用对应一个子问题。子问题由递归参数确定。

示例：Fibonacci 的子问题 fib(i)，由参数 i 确定。

什么是子问题重叠？

定义：如果同一子问题在递归过程中被多次调用，称为子问题重叠。

判断标准：

画出递归树（或调用图）
检查是否有相同的节点出现多次

Fibonacci 的递归树：

fib(5) → fib(4), fib(3)
fib(4) → fib(3), fib(2)  ← fib(3) 重复！
fib(3) → fib(2), fib(1)  ← fib(2) 重复！

什么是记忆化？

定义：记忆化是一种优化技术，通过缓存已计算的子问题结果，避免重复计算。

核心机制：

第一次计算子问题时，将结果存入缓存（memo）
后续调用时，直接从缓存读取，不再重新计算

类比：备忘录。第一次算 fib(10) 时，把结果记在备忘录上；下次再需要 fib(10)，直接查阅备忘录。

子问题图：DAG 视角

定义：子问题图是一个有向无环图（DAG），每个节点是一个子问题，每条边表示依赖关系。

Fibonacci 的子问题图：

fib(5) → fib(4)
fib(5) → fib(3)
fib(4) → fib(3)
fib(4) → fib(2)
fib(3) → fib(2)
fib(3) → fib(1)
fib(2) → fib(1)
fib(2) → fib(0)

关键观察：

fib(3) 有两条入边：来自 fib(5) 和 fib(4) → 说明被调用两次
这个图是 DAG（无环）→ 可以按拓扑序计算

时间复杂度的子问题图视角

定理：动态规划的时间复杂度 = O(子问题数 × 每个子问题的计算代价)。

证明：

每个子问题只计算一次（记忆化保证）
每个子问题的计算需要访问其依赖（边）
总时间 = Σ(每个子问题的计算代价)

Fibonacci 应用：

子问题数：n+1 个（fib(0) 到 fib(n))
每个子问题计算代价：O(1)（一次加法）
总时间：O(n)

算法实现：三种实现方式对比

方法一：记忆化递归（自顶向下）

python

def fib_memo(n):
    memo = {}
    
    def fib(k):
        if k in memo:
            return memo[k]
        if k <= 1:
            memo[k] = k
        else:
            memo[k] = fib(k-1) + fib(k-2)
        return memo[k]
    
    return fib(n)

特点：

形式上仍是递归（符合直觉）
通过 memo 避免重复计算
调用顺序：从大问题开始，逐步分解

方法二：迭代填表（自底向上）

python

def fib_iter(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

特点：

明确的计算顺序（i 从 2 到 n）
每个子问题只计算一次
容易理解"填表"过程

方法三：空间优化

python

def fib_optimized(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for i in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

特点：

空间复杂度：O(1)（只保留前两个值）
利用递推式特性：dp[i] 只依赖 dp[i-1] 和 dp[i-2]

三种方法对比

方法	时间复杂度	空间复杂度	实现难度	适用场景
朴素递归	O(φ^n)	O(n) 栈深度	简单	不适用（太慢）
记忆化递归	O(n)	O(n) memo	中等	子问题顺序不明确
迭代填表	O(n)	O(n) dp 表	简单	子问题顺序明确
空间优化	O(n)	O(1)	中等	只需前一状态

何时用记忆化？何时用迭代？

记忆化：子问题的依赖顺序不明确时（如某些图问题）
迭代：子问题可以明确排序时（如 Fibonacci、LCS）

正确性分析：为什么记忆化保证正确？

记忆化不改变计算结果

定理：记忆化版本的输出与朴素递归版本相同。

证明思路：

记忆化的 memo 存储的是"正确计算的结果"
第一次计算时，执行的是与朴素递归相同的逻辑
后续调用时，直接返回已存储的正确结果

反证法：假设记忆化版本输出错误。

设第一次计算 fib(k) 时，memo[k] 存储了错误值 v。

但计算 fib(k) 的过程与朴素递归相同：

若 k ≤ 1，memo[k] = k（正确）
若 k > 1，memo[k] = fib(k-1) + fib(k-2)（递归调用正确）

矛盾。□

为什么记忆化有效？

条件一：子问题重叠。

若无重叠，记忆化无意义——每个子问题只调用一次，memo 从未被复用。

条件二：子问题数量有限。

若子问题数无限，memo 会无限增长，空间不可控。

Fibonacci 满足条件：

子问题重叠：fib(k) 被多次调用
子问题数有限：只有 fib(0) 到 fib(n)，共 n+1 个

复杂度分析

朴素递归的复杂度

时间复杂度：O(φ^n)，其中 φ ≈ 1.618（黄金比例）。

推导：

fib(n) 的调用次数 ≈ fib(n) 的值
fib(n) ≈ φ^n / √5

空间复杂度：O(n)（递归栈深度）。

记忆化版本的复杂度

时间复杂度：O(n)。

推导：

子问题数：n+1 个
每个子问题计算一次，代价 O(1)
总时间：O(n)

空间复杂度：O(n)（memo 表）。

空间优化版本的复杂度

时间复杂度：O(n)。

空间复杂度：O(1)（只保留前两个值）。

关键洞察：递推式 dp[i] = dp[i-1] + dp[i-2] 只依赖前两个状态。

反例：为什么 quicksort 不能用 DP 优化？

Quicksort 的递归

python

def quicksort(arr, left, right):
    if left >= right:
        return
    pivot = partition(arr, left, right)
    quicksort(arr, left, pivot - 1)
    quicksort(arr, pivot + 1, right)

子问题：quicksort(arr, l, r)——对 arr[l:r] 排序。

为什么没有子问题重叠？

关键观察：每次 partition 后，子数组是不同的。

例如：

quicksort(arr, 0, 10) → pivot = 5
子问题：quicksort(arr, 0, 4) 和 quicksort(arr, 6, 10)
这两个子问题的参数不同，不会重复调用

本质原因：Quicksort 的每次递归调用处理的是不同的子数组，子问题参数不重叠。

对比 Fibonacci

问题	子问题参数	是否重叠
Fibonacci	fib(k)，k 固定	✓ 同一 k 被多次调用
Quicksort	quicksort(arr, l, r)	✗ 每次调用参数不同

结论：DP 优化（记忆化）只对子问题重叠的问题有效。

变式与延伸

变式 1：三阶 Fibonacci（Tribonacci）

定义：T(n) = T(n-1) + T(n-2) + T(n-3)，T(0)=0, T(1)=1, T(2)=1。

python

def tribonacci(n):
    if n <= 1:
        return n
    if n == 2:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    return dp[n]

空间优化：保留前三个值即可，O(1) 空间。

变式 2：爬楼梯问题

问题：每次可以爬 1 级或 2 级楼梯，n 级楼梯有多少种爬法？

直觉：这其实就是 Fibonacci！

f(n) = f(n-1) + f(n-2)
f(1) = 1（一种方法：爬 1 级）
f(2) = 2（两种方法：爬 1+1 或爬 2）

答案：f(n) = fib(n+1)。

变式 3：带代价的爬楼梯

问题：每级楼梯有代价 cost[i]，求最小总代价到达顶层。

状态定义：dp[i] = 到达第 i 级的最小代价。

递推式：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。

python

def min_cost_stairs(cost):
    n = len(cost)
    dp = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    return dp[n]

常见错误诊断

错误 1：忘记边界条件

python

# 错误示例
def fib_wrong(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# 错误：n=0 时，dp[1] = 1 会越界

正确做法：先检查 n ≤ 1 的情况。

错误 2：记忆化版本忘记返回缓存值

python

# 错误示例
memo = {}
def fib_memo_wrong(n):
    if n in memo:
        # 缺少 return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib_memo_wrong(n-1) + fib_memo_wrong(n-2)
    return memo[n]

后果：即使 memo 中有值，仍会重新计算。

错误 3：子问题图理解错误

有人误以为"子问题图有环"。

澄清：子问题图是 DAG（无环）。因为递归定义保证了依赖的单向性：fib(k) 依赖 fib(k-1) 和 fib(k-2)，不会反过来。

LLM 连接：KV-Cache 与记忆化同构

KV-Cache 的本质

KV-Cache：在 LLM 推理时，缓存已计算的 Key-Value 向量，避免重复计算。

类比 Fibonacci 记忆化：

Fibonacci：缓存 fib(k) 的值，避免重复计算
KV-Cache：缓存 token 的 K-V 向量，避免重复计算

共同条件：

子问题重叠 → prefix reuse（相同前缀被多次查询）
参数有限 → token 数有限

为什么这个连接重要？

理解 DP → 理解 KV-Cache 有效模式：

识别 prefix reuse：哪些 prompt 的前缀会被多次使用？
设计缓存策略：哪些 K-V 需要保留？哪些可以丢弃？
优化推理效率：类似空间优化，只保留必要的缓存

练习

基本理解

概念解释：什么是"子问题重叠"？用自己的话解释。
画图验证：画出 fib(7) 的递归树，标注哪些节点被多次调用。
对比分析：为什么 Fibonacci 有子问题重叠，Quicksort 没有？

方法应用

记忆化实现：实现 fib(100) 的记忆化版本，对比朴素递归的运行时间。
空间优化：实现 Tribonacci 的空间优化版本（只保留前三个值）。
爬楼梯变式：实现"带代价的爬楼梯"问题。

错误诊断

诊断错误：给定一个"忘记边界条件"的 DP 代码，预测会发生什么错误。
记忆化遗漏：如果记忆化版本忘记在第一次计算时存入 memo，会发生什么？
复杂度误判：有人说"记忆化把递归优化到 O(1)"，诊断这个错误说法。

方案比较

记忆化 vs 迭代：对比两种实现方式，何时用记忆化更合适？
空间权衡：什么时候可以空间优化？什么时候不能？
DP vs 分治：DP 和分治的区别是什么？为什么 DP 需要子问题重叠？

开放设计

新问题判断：给定一个问题（如"汉诺塔"），判断是否适合用 DP 优化。
状态设计：为"带代价的爬楼梯"设计状态，写出递推式。
LLM 连接：分析 KV-Cache 的"prefix reuse"条件，类比 Fibonacci 的子问题重叠。

综合应用

钢条切割：用记忆化实现钢条切割问题，对比朴素递归的效率。
组合问题：设计一个问题，让记忆化无效（无子问题重叠）。
真实问题：用 DP 解决实际问题：计算字符串的不同子序列数。

思考题

为什么 Fibonacci 递归这么慢？

不是因为递归本身，而是因为子问题重叠。fib(k) 被多次调用，导致计算次数指数增长。记忆化后，每个 fib(k) 只计算一次，时间 O(n)。

为什么 Quicksort 不能用 DP 优化？

因为 Quicksort 的子问题不重叠。每次 partition 后，子数组的参数不同，不会重复调用同一个子问题。

记忆化和迭代哪个更好？

取决于子问题顺序：

顺序明确（如 Fibonacci）：迭代更直观
顺序不明确（如某些图问题）：记忆化更灵活

过渡：子问题重叠是 DP 的必要条件，但不是充分条件。下一节：为什么最长路径不能用 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.

6.1 子问题与重叠——朴素递归的困境 ​

问题情境：Fibonacci 的"指数陷阱" ​

面试现场的尴尬 ​

第一次困惑：规模增长 vs 时间增长 ​

第二次困惑：不是"递归慢"，而是"重复计算" ​

直观思路：把重复的部分"记住" ​

第一次改进：引入"备忘录" ​

第二次改进：不用递归，直接填表 ​

第三次改进：还能更省空间吗？ ​

规范定义：子问题重叠与记忆化 ​

什么是子问题？ ​

什么是子问题重叠？ ​

什么是记忆化？ ​

子问题图：DAG 视角 ​

时间复杂度的子问题图视角 ​

算法实现：三种实现方式对比 ​

方法一：记忆化递归（自顶向下） ​

方法二：迭代填表（自底向上） ​

方法三：空间优化 ​

三种方法对比 ​

正确性分析：为什么记忆化保证正确？ ​

记忆化不改变计算结果 ​

为什么记忆化有效？ ​

复杂度分析 ​

朴素递归的复杂度 ​

记忆化版本的复杂度 ​

空间优化版本的复杂度 ​

反例：为什么 quicksort 不能用 DP 优化？ ​

Quicksort 的递归 ​

为什么没有子问题重叠？ ​

对比 Fibonacci ​

变式与延伸 ​

变式 1：三阶 Fibonacci（Tribonacci） ​

变式 2：爬楼梯问题 ​

变式 3：带代价的爬楼梯 ​

常见错误诊断 ​

错误 1：忘记边界条件 ​

错误 2：记忆化版本忘记返回缓存值 ​

错误 3：子问题图理解错误 ​

LLM 连接：KV-Cache 与记忆化同构 ​

KV-Cache 的本质 ​

为什么这个连接重要？ ​

练习 ​

基本理解 ​

方法应用 ​

错误诊断 ​

方案比较 ​

开放设计 ​

综合应用 ​

思考题 ​

6.1 子问题与重叠——朴素递归的困境

问题情境：Fibonacci 的"指数陷阱"

面试现场的尴尬

第一次困惑：规模增长 vs 时间增长

第二次困惑：不是"递归慢"，而是"重复计算"

直观思路：把重复的部分"记住"

第一次改进：引入"备忘录"

第二次改进：不用递归，直接填表

第三次改进：还能更省空间吗？

规范定义：子问题重叠与记忆化

什么是子问题？

什么是子问题重叠？

什么是记忆化？

子问题图：DAG 视角

时间复杂度的子问题图视角

算法实现：三种实现方式对比

方法一：记忆化递归（自顶向下）

方法二：迭代填表（自底向上）

方法三：空间优化

三种方法对比

正确性分析：为什么记忆化保证正确？

记忆化不改变计算结果

为什么记忆化有效？

复杂度分析

朴素递归的复杂度

记忆化版本的复杂度

空间优化版本的复杂度

反例：为什么 quicksort 不能用 DP 优化？

Quicksort 的递归

为什么没有子问题重叠？

对比 Fibonacci

变式与延伸

变式 1：三阶 Fibonacci（Tribonacci）

变式 2：爬楼梯问题

变式 3：带代价的爬楼梯

常见错误诊断

错误 1：忘记边界条件

错误 2：记忆化版本忘记返回缓存值

错误 3：子问题图理解错误

LLM 连接：KV-Cache 与记忆化同构

KV-Cache 的本质

为什么这个连接重要？

练习

基本理解

方法应用

错误诊断

方案比较

开放设计

综合应用

思考题