Dynamic Programming

定义（中文）/ Definition

动态规划：一种常用的算法设计思想，把一个复杂问题分解为相互重叠的子问题，先求解子问题并保存结果（记忆化或表格法），从而高效地得到原问题的最优解。常见于“最短路径、背包、序列比对、区间最优”等问题。（该术语在不同语境下也可简称为 DP。）

发音（IPA）/ Pronunciation

/daɪˈnæmɪk ˈproʊɡræmɪŋ/

例句 / Examples

Dynamic programming can solve the Fibonacci sequence efficiently.
动态规划可以高效地求解斐波那契数列。

By using dynamic programming, we computed the minimum edit distance between two strings while avoiding repeated work.
通过动态规划，我们在避免重复计算的同时求出了两个字符串的最小编辑距离。

词源（中文）/ Etymology

“Dynamic programming”这一术语由美国数学家 Richard Bellman 在 20 世纪 50 年代提出。“dynamic（动态的）”在这里更多强调“分阶段决策、逐步推进”的过程；“programming”在当时的学术语境里常指“规划/方案制定（planning）”，不单是今天意义上的“写程序”。因此它更接近“动态规划法”的含义。

相关词汇 / Related Words

• Algorithm
• Optimization
• Recursion
• Memoization
• Greedy
• Backtracking
• Subproblem
• Shortest Path

文学与名著用例 / Literary & Notable Works

• Richard Bellman — Dynamic Programming（1957）：该领域奠基性专著，系统提出与发展动态规划方法。
• Thomas H. Cormen et al. — Introduction to Algorithms（《算法导论》）：以多个经典例题（如钢条切割、矩阵链乘法等）讲解动态规划。
• Jon Kleinberg & Éva Tardos — Algorithm Design：在算法设计章节中以动态规划作为核心策略之一，覆盖路径与序列类问题。
• Donald E. Knuth — The Art of Computer Programming（《计算机程序设计艺术》相关卷）：涉及与动态规划相关的最优化与递推思想，并在算法分析语境中出现该术语或相关方法。