动态规划

动态规划是一种算法设计范式，通过解决具有最优子结构和重叠子问题的问题，对每个子问题只求解一次并存储其结果以供重用，从而将指数级的重复计算转化为多项式时间计算。

Definition

动态规划是一种通过递归地定义其值（基于重叠子问题）来解决优化或计数问题的方法，它对每个不同的子问题只计算一次，并缓存结果以便重用，而不是重新计算。

Scope

本主题涵盖了使动态规划适用的两个标志性特征——最优子结构和重叠子问题——以及两种实现方式：自上而下的记忆化和自下而上的制表法。它包括了经典问题，如最长公共子序列、编辑距离、背包问题、矩阵链乘法和最短路径动态规划，以及状态空间设计和时间与空间权衡分析。它不包括图算法中处理的特定于图的最短路径方法，尽管它们共享相同的基本原理。

Core questions

• 问题是否具有最优子结构，使得最优解可以由最优子解构建？
• 如何定义子问题集（状态空间），使得每个子问题只递归多项式次？
• 解决方案应该采用自上而下的记忆化还是自下而上的制表法实现？
• 如何重建表格以恢复实际的最优解，而不仅仅是其值？
• 当每一步只需要表格的一部分时，如何减少空间？

Key concepts

• 最优子结构
• 重叠子问题
• 最优性原理
• 记忆化
• 制表法
• 状态空间和递推关系
• 最长公共子序列
• 编辑距离
• 背包问题

Key theories

最优性原理

贝尔曼的最优性原理指出，最优策略具有这样的性质：无论初始状态和决策如何，其余的决策都必须构成针对由此产生状态的最优策略——这是动态规划递推关系的正式基础。

记忆化与制表法

动态规划可以通过向递归公式添加缓存（记忆化）自上而下地实现，或者通过按依赖顺序填充表格（制表法）自下而上地实现；两者都只计算每个子问题一次，但在评估顺序和空间行为上有所不同。

Clinical relevance

动态规划在实践中无处不在：计算生物学中的序列比对（Needleman-Wunsch，Smith-Waterman）、拼写检查和版本控制差异中的编辑距离、语音识别和通信中的维特比算法，以及运筹学、金融和强化学习中的动态规划。

History

理查德·贝尔曼（Richard Bellman）于20世纪50年代在兰德公司（RAND Corporation）工作期间开发了动态规划，部分原因是为了让研究资助者更容易接受这个名称。最优性原理和贝尔曼方程成为运筹学、控制理论和计算机科学的基础，该技术后来在算法教科书中被编纂为核心算法范式。

Key figures

• Richard Bellman
• Thomas H. Cormen
• Jon Kleinberg
• Éva Tardos

Seminal works

• bellman1957
• cormen2009

Frequently asked questions

分治法和动态规划有什么区别？

两者都将问题分解为子问题，但分治法的子问题是独立的且只解决一次，而动态规划的子问题是重叠的，如果采用朴素递归，则会被重复计算多次。动态规划缓存子问题解以避免这种重复计算。

动态规划何时不适用？

它需要最优子结构和多项式大小的独立子问题集。如果问题缺乏最优子结构，或者自然状态空间是指数级的且无法压缩，那么动态规划要么不正确，要么不再高效。