动态规划

概述

动态规划（Dynamic Programming, DP）是一种通过记忆化（memoization）或自底向上填表来避免重复计算的算法设计策略。其核心在于问题必须具备最优子结构和重叠子问题两个要素。与贪心算法不同，动态规划会考虑所有可能的选择而非仅选局部最优；与分治法不同，动态规划的子问题是重叠的。

定义

动态规划（Dynamic Programming）

动态规划是一种将复杂问题分解为若干重叠子问题，通过存储子问题的解来避免重复计算的算法策略。动态规划的两个核心要素：

1. 最优子结构（Optimal Substructure）：问题的最优解包含其子问题的最优解
2. 重叠子问题（Overlapping Subproblems）：递归求解时，相同的子问题会被反复计算

动态规划的两种实现方式：

• 自顶向下（记忆化搜索）：递归 + 缓存已计算的子问题解
• 自底向上（填表法）：按子问题规模从小到大依次求解，填入表格

核心性质

性质	描述	备注
最优子结构	最优解包含子问题的最优解	与贪心算法共享此性质
重叠子问题	递归过程中子问题被反复计算	这是使用 DP 的动机
记忆化/填表	存储子问题解以避免重复计算	将指数级复杂度降为多项式级
无后效性	某阶段的状态一旦确定，后续决策不影响之前的状态	DP 适用性的关键条件
考虑所有选择	枚举所有可能的决策，而非只选局部最优	区别于贪心算法

应用场景

动态规划在算法导论中的经典应用：

• 最长公共子序列（LCS）：$O(mn)$ 时间和空间，用于文本比较、DNA 序列比对
• 矩阵链乘法：$O(n^3)$ 时间，找到最优括号化方案
• 最优二叉搜索树：$O(n^3)$ 时间，构造平均搜索代价最小的 BST
• 0-1 背包问题：$O(nW)$ 时间，贪心算法无法解决
• Fibonacci 数列：朴素递归 $O({\varphi }^n)$ → DP 优化至 $O(n)$
• 编辑距离：$O(mn)$ 时间，用于拼写检查、字符串匹配

动态规划 vs 贪心 vs 分治

比较维度	动态规划	贪心算法	分治法
子问题重叠	重叠	通常不重叠	不重叠
决策方式	考虑所有选择	选局部最优	递归分解
最优性保证	通常保证全局最优	不一定	取决于问题
存储需求	需要表格	通常不需要	通常不需要
典型应用	LCS、背包	Dijkstra、Huffman	归并排序、Strassen

参见

• 分治法 — 子问题不重叠时的分解策略
• 贪心算法 — 只选局部最优的简化策略
• 递归关系式 — DP 的状态转移方程本质上是递推关系
• Fibonacci数 — DP 优化的经典示例
• 摊还分析 — 分析 DP 数据结构操作序列的代价