Dynamic Programming

释义 Definition

动态规划：一种把复杂问题分解为许多重叠子问题来求解的算法思想。通过记录子问题的最优结果（常用“表格/数组”或“记忆化搜索”），避免重复计算，从而高效地得到整体最优解。常见于最短路径、背包问题、序列比对、编辑距离等。

发音 Pronunciation (IPA)

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

例句 Examples

Dynamic programming can solve the shortest path problem efficiently.
动态规划可以高效地解决最短路径问题。

By defining a recurrence relation and caching intermediate results, the algorithm uses dynamic programming to compute the minimum edit distance between two strings.
通过定义递推关系并缓存中间结果，该算法使用动态规划来计算两个字符串之间的最小编辑距离。

词源 Etymology

“Dynamic programming”这一术语通常归功于美国数学家 Richard Bellman（理查德·贝尔曼）在20世纪50年代提出并推广。这里的 dynamic 更接近“随阶段/时间变化的决策过程”，programming 指“规划/求解方案（最优化计算）”，并非现代日常所说的“写程序”。因此中文常译为“动态规划”。

相关词 Related Words

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

文学与经典著作 Literary Works

• Richard Bellman, Dynamic Programming（1957）
• Thomas H. Cormen et al., Introduction to Algorithms（常称 CLRS，含大量动态规划章节）
• Donald E. Knuth, The Art of Computer Programming（多处讨论相关思想与递推/最优化问题）
• Robert Sedgewick & Kevin Wayne, Algorithms（含动态规划与典型应用示例）