重叠子问题

概述

重叠子问题是指在递归求解过程中，同一个子问题被反复计算多次的现象。这是动态规划区别于分治法的关键特征。通过备忘录（自顶向下）或自底向上表格技术，可以消除冗余计算，将指数级时间复杂度降低到多项式级。

定义

重叠子问题（Overlapping Subproblems）

当一个递归算法不断将问题分解为子问题时，如果不同的递归分支会求解完全相同的子问题实例，则称该问题具有重叠子问题性质。

设递归算法的递归树中，子问题 $(i)$ 被访问的次数为 $T(i)$。若存在某个子问题 $(i)$ 使得 $T(i)>1$，则存在重叠子问题。

核心性质

1. 与分治法的本质区别

分治法（如归并排序、快速排序）的子问题是互不重叠的——每个子问题只被求解一次。而动态规划面对的问题中，子问题空间虽然规模有限，但递归过程中会反复遇到相同的子问题。

特征	分治法	动态规划
子问题关系	互不重叠	大量重叠
子问题数量	递归树的所有节点	有限个子问题（表格大小）
典型复杂度	$O(n\log n)$	$O(n^2)$ 或 $O(n^3)$

2. 钢条切割中的重叠示例

在 钢条切割 问题中，朴素递归调用 CUT-ROD(p, n) 时，子问题 $r[1]$（长度为1的钢条的最大收益）被重复计算多次。具体地，计算 $r[n]$ 时，$r[1]$ 会在以下路径中被反复求解：

• $r[n]\to r[n-1]\to r[n-2]\to \cdots \to r[1]$
• $r[n]\to r[n-2]\to r[n-3]\to \cdots \to r[1]$
• $r[n]\to r[n-3]\to \cdots \to r[1]$
• …（共 $n-1$ 条路径到达 $r[1]$）

这导致朴素递归的时间复杂度为 $O(2^n)$，而子问题总数仅为 $n$ 个。

3. 备忘录方法（自顶向下）

备忘录方法维护一个表格 $memo[\mathrm{1..}n]$，初始值为某个哨兵值（如 $-\infty$）。每次求解子问题前先查表，若已计算则直接返回；否则计算后存入表格。

MEMOIZED-CUT-ROD(p, n, r):
    if r[n] >= 0:
        return r[n]
    if n == 0:
        q = 0
    else:
        q = -∞
        for i = 1 to n:
            q = max(q, p[i] + MEMOIZED-CUT-ROD(p, n-i, r))
    r[n] = q
    return q

时间复杂度：$O(n^2)$（每个子问题只计算一次，每次计算需要 $O(n)$ 的时间）。

4. 自底向上方法

自底向上方法按照子问题的规模从小到大依次填表，确保计算每个子问题时，它所依赖的更小子问题已经计算完毕。

BOTTOM-UP-CUT-ROD(p, n):
    r[0] = 0
    for j = 1 to n:
        q = -∞
        for i = 1 to j:
            q = max(q, p[i] + r[j-i])
        r[j] = q
    return r[n]

时间复杂度：$O(n^2)$，空间复杂度：$O(n)$。

5. 两种方法的等价性

备忘录方法和自底向上方法具有相同的渐近时间复杂度。它们的区别在于：

• 备忘录：只计算实际需要的子问题（可能跳过某些子问题），但存在递归调用的常数开销
• 自底向上：计算所有子问题，无递归开销，通常实际运行更快

章节扩展

• 14.1 钢条切割 — 钢条切割问题的完整求解过程
• 14.3 动态规划设计要素 — 重叠子问题在动态规划设计中的角色
• 动态规划 — 动态规划完整方法论

参见

• 最优子结构 — 动态规划的另一个核心性质
• 钢条切割 — 重叠子问题的典型示例
• 矩阵链乘法 — 另一个具有重叠子问题的经典问题