动态规划

概述

动态规划（Dynamic Programming）是一种通过分解问题和记忆化来高效求解最优化问题的算法设计范式。其核心思想是将复杂问题分解为相互重叠的子问题，每个子问题只求解一次并存储结果，从而避免指数级的冗余计算。动态规划要求问题同时具备最优子结构和重叠子问题两个核心性质。

定义

动态规划（Dynamic Programming）

动态规划是一种将复杂问题分解为更小的、相互重叠的子问题来求解的方法。它通过存储子问题的解（通常以表格形式），确保每个子问题只被求解一次，从而将指数级时间复杂度降低到多项式级。

“Dynamic Programming” 这一名称由 Richard Bellman 于 1950 年代提出，其中 “Programming” 指的是”表格填写”（tabulation），而非计算机编程。

核心性质

1. 动态规划的四步设计法

开发一个动态规划算法需要经过以下四个步骤：

1. 刻画最优解的结构：分析问题的最优解是否包含子问题的最优解（验证最优子结构）
2. 递归定义最优解的值：用子问题的最优解来递归地定义原问题最优解的代价
3. 计算最优解的值：通常采用自底向上的方式，按子问题的规模从小到大依次填写表格
4. 构造最优解：通过回溯表格中的决策信息，构造出具体的最优解

2. 两个核心性质

动态规划的有效性依赖于以下两个性质：

• 最优子结构：原问题的最优解包含子问题的最优解。这意味着我们可以通过组合子问题的最优解来构造原问题的最优解。
• 重叠子问题：递归求解时，同一子问题会被多次遇到。这意味着存储子问题的解可以带来显著的效率提升。

3. 与贪心算法的本质区别

特征	动态规划	贪心算法
决策方式	先求解后选择	先选择后求解
子问题依赖	考虑所有子问题	只考虑一个子问题
适用条件	最优子结构 + 重叠子问题	贪心选择性质 + 最优子结构
全局最优性	保证	不一定保证
时间复杂度	通常较高（$O(n^2)$ 或 $O(n^3)$）	通常较低（$O(n\log n)$ 或 $O(n)$）

动态规划在每一步都考虑所有可能的选择，然后基于子问题的最优解做出决策；贪心算法则在每一步直接做出局部最优选择，不再回溯。

4. 两种实现方式

• 自底向上（Bottom-Up）：按子问题规模从小到大依次填写表格。确保计算每个子问题时，它所依赖的更小子问题已经计算完毕。通常效率更高，无递归开销。
• 自顶向下（Top-Down / 备忘录）：在递归过程中记录已计算的子问题结果。只计算实际需要的子问题，但存在递归调用的常数开销。

5. 经典问题分类

问题类型	代表问题	时间复杂度	空间复杂度
线性DP	钢条切割	$O(n^2)$	$O(n)$
区间DP	矩阵链乘法、最优二叉搜索树	$O(n^3)$	$O(n^2)$
序列DP	最长公共子序列	$O(mn)$	$O(mn)$
背包问题	0-1背包、完全背包	$O(nW)$	$O(nW)$

章节扩展

• 14.1 钢条切割 — 动态规划的入门示例
• 14.2 矩阵链乘法 — 区间型动态规划
• 14.3 动态规划设计要素 — 设计方法论的系统总结
• 14.4 最长公共子序列 — 序列型动态规划
• 14.5 最优二叉搜索树 — 树结构上的动态规划

参见

• 最优子结构 — 动态规划的核心性质之一
• 重叠子问题 — 动态规划的另一个核心性质
• 贪心算法 — 另一种最优化算法范式
• 贪心选择性质 — 贪心算法的核心性质
• 替换论证 — 贪心正确性证明技术