重叠子问题

重叠子问题 (Overlapping Subproblems)

重叠子问题 (Overlapping Subproblems) 是动态规划 (Dynamic Programming) 的两个核心适用条件之一（另一个是最优子结构）。它描述的是：在递归求解一个问题时，同一个子问题被反复计算多次，而非每次遇到时都是全新的。动态规划通过备忘录 (Memoization) 或自底向上列表 (Tabulation) 将每个子问题的解存储起来，从而将指数级时间复杂度的朴素递归降为多项式级。

直观理解

考虑一个典型的递归问题：计算第 $n$ 个斐波那契数 $F(n) = F(n-1) + F(n-2)$，其中 $F(0)=0, F(1)=1$。若直接用递归实现，计算 $F(5)$ 需要：

• 计算 $F(4)$ 和 $F(3)$
• 计算 $F(4)$ 又需要 $F(3)$ 和 $F(2)$
• $F(3)$ 被重复计算了两次
• 更底层的 $F(2)$、$F(1)$、$F(0)$ 被重复的次数更多

随着 $n$ 增大，重复计算的次数呈指数增长，时间复杂度为 $O(2^n)$。而动态规划将每个 $F(k)$ 只计算一次并存储，后续直接查表，时间复杂度降为 $O(n)$。

形式定义

设原问题 $P$ 的递归解可表示为一系列子问题 $\{p_1, p_2, \ldots, p_k\}$ 的组合。若子问题集合中存在 $p_i = p_j$（即两个不同递归路径上出现了完全相同的子问题），则称该问题具有重叠子问题性质。

更形式化地，令 $T(n)$ 为解决规模为 $n$ 的问题所需调用的子问题总数。若 $T(n)$ 中互不相同的子问题数量远小于 $T(n)$ 本身，则重叠显著。

与分治法的对比

重叠子问题是动态规划区别于分治法 (Divide and Conquer) 的关键特征：

• 分治法（如归并排序、快速排序）：子问题相互独立，每个子问题至多被求解一次，不存在重复。时间复杂度由递归树的节点数自然决定。
• 动态规划（如斐波那契、最短路径、编辑距离）：子问题高度重叠，若不存储中间结果，将导致大量重复计算。

两者都依赖于最优子结构，但仅当前者同时具备重叠子问题时，动态规划带来的效率提升才是决定性的。

两种消除策略

1. 备忘录法（自上而下）：保留递归结构，但用一个缓存表记录已求解子问题的答案。每次进入递归前先查表，命中则直接返回，未命中则计算并存入。

1. 列表法（自下而上）：显式定义子问题的求解顺序，从小规模逐步构建到原问题。通常用数组或矩阵迭代填充，避免递归调用的栈开销。

两种策略的时间复杂度相同，空间复杂度均可通过优化（如滚动数组）进一步压缩。

经济学与运筹学中的应用

在经济学中，重叠子问题的概念直接体现于贝尔曼方程 (Bellman Equation)。无限期动态优化问题中，值函数 $V(s)$ 满足：

其中 $s$ 为当前状态，$s'$ 为下一期状态。同一个状态 $s$ 可能经由不同决策路径到达，其值函数 $V(s)$ 是所有以 $s$ 为起点的子问题的共同解。若不加缓存，同一状态的价值会被反复评估。

类似地，在消费平滑 (Consumption Smoothing)、资产定价中的递归偏好模型、以及博弈论中的递归博弈均衡计算中，状态空间的重复访问使得重叠子问题性质天然成立，动态规划因此成为求解此类模型的标配工具。