Overlapping Subproblems

释义 Definition

“overlapping subproblems”（重叠子问题）：指在用递归/分治来解决问题时，许多子问题会重复出现（同一个子问题被反复计算）。这是动态规划（Dynamic Programming）适用的重要特征之一：通过记忆化或表格法把已算过的子问题结果保存下来，避免重复计算，从而显著提高效率。

发音 Pronunciation (IPA)

/ˌoʊvərˈlæpɪŋ ˈsʌbˌprɑːbləmz/

例句 Examples

Dynamic programming works well when there are overlapping subproblems.
当存在重叠子问题时，动态规划就很有效。

In computing Fibonacci numbers recursively, the same smaller cases are recomputed many times, which is why overlapping subproblems make memoization so powerful.
用递归计算斐波那契数时，同样的更小情况会被反复重算，这就是为什么重叠子问题会让“记忆化”变得非常强大。

词源 Etymology

该术语由两部分组成：overlapping（重叠的）来自 overlap，表示“部分覆盖、重复”；subproblems（子问题）由 *sub-*（“次级、下层”）+ problem（问题）构成。合起来直观表达：一个大问题拆分后得到的若干子问题之间存在“重复/重叠”的部分，需要多次求解同一子问题。

相关词 Related Words

• Dynamic Programming
• Memoization
• Optimal Substructure
• Recursion
• Divide And Conquer
• Tabulation
• Subproblem
• Caching

文献与作品 Literary Works

• Introduction to Algorithms（《算法导论》, Cormen/Leiserson/Rivest/Stein）——动态规划章节常用“overlapping subproblems”作为核心判据之一。
• Algorithm Design（《算法设计》, Kleinberg & Tardos）——在DP设计思想中反复强调子问题复用与重叠。
• Dynamic Programming and Optimal Control（《动态规划与最优控制》, Dimitri P. Bertsekas）——从最优化视角系统讨论子问题结构与重复计算。
• Competitive Programming（《算法竞赛入门经典/竞赛编程》系列, Halim 等）——以竞赛题为例讲解如何利用重叠子问题进行记忆化/递推优化。