Subproblem

定义 Definition

subproblem（子问题）：在解决一个更大问题（尤其是数学、算法与计算机科学中的优化/递归问题）时，被拆分出来的较小问题。常见于分治与动态规划，子问题的解可被组合或复用以得到原问题的解。（在日常英语中也可泛指“更大任务中的一个小问题”，但最常见用法在技术语境。）

发音 Pronunciation (IPA)

/sbprblm/（美式）
/sbprblm/（英式）

例句 Examples

The algorithm breaks the task into smaller subproblems.
该算法把任务拆分成更小的子问题。

In dynamic programming, we store the answer to each subproblem so we don’t compute it again, which greatly reduces the running time.
在动态规划中，我们保存每个子问题的答案以避免重复计算，从而大幅降低运行时间。

词源 Etymology

由前缀 **sub-**（“在下、次级、分支”）+ problem（“问题”）构成，字面意思是“次级/下层的问题”。在20世纪算法与运筹学发展中，该词在“把复杂问题分解为可管理部分”的语境里逐渐固定为技术术语。

相关词 Related Words

• Decomposition
• Divide-and-conquer
• Dynamic
• Recursion
• Memoization
• Subtask
• Optimization
• Overlap

文学与经典作品 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein；常称 CLRS）：在分治与动态规划章节中频繁使用“subproblem”讨论子问题划分与递推关系。
• Richard Bellman, Dynamic Programming：动态规划的奠基著作，核心概念之一就是把问题拆成可复用的子问题。
• Donald E. Knuth, The Art of Computer Programming：在递归、分解与算法分析相关内容中常见“subproblem”这一表述。
• Jon Kleinberg & va Tardos, Algorithm Design：在动态规划设计模式中系统讲解“子问题定义状态转移”的思路。