动态规划 vs 贪心算法
概述
动态规划（Dynamic Programming）和贪心算法（Greedy Algorithm）都是求解优化问题的经典方法，两者都利用最优子结构性质，但在求解顺序和适用条件上有本质区别。动态规划自底向上地考虑所有子问题，而贪心算法在每一步做出局部最优选择。
对比表格
| 维度 | 动态规划 | 贪心算法 |
|---|---|---|
| 求解顺序 | 先求解子问题，再基于子问题的解做出选择 | 先做出选择，再求解剩下的子问题 |
| 子问题依赖 | 子问题之间可能相互依赖，需要求解所有相关子问题 | 子问题之间相互独立，做出选择后只需求解一个子问题 |
| 选择数量 | 在每一步隐式地考察所有可能的选择 | 在每一步显式地做出一个选择 |
| 前提条件 | 需要最优子结构 + 重叠子问题 | 需要最优子结构 + 贪心选择性质 |
| 贪心选择性质 | 不要求贪心选择性质 | 必须满足贪心选择性质（局部最优选择能导致全局最优） |
| 最优性保证 | 总能得到最优解（前提是正确建模） | 仅在满足贪心选择性质时保证最优解 |
| 时间复杂度 | 通常较高（需填表， 或更高） | 通常较低（ 或更低） |
| 空间复杂度 | 通常需要 或更多空间存储子问题解 | 通常只需 或 额外空间 |
| 适用范围 | 广泛（几乎所有具有最优子结构的问题） | 较窄（需要额外满足贪心选择性质） |
关键差异
1. 求解顺序的本质区别
这是两种方法最根本的区别：
- 动态规划：采用自底向上的策略。先求解所有子问题，将结果存入表格，然后逐步组合子问题的解来构建原问题的解。在每一步，算法”回顾”已求解的子问题来做出最优选择。
- 贪心算法：采用自顶向下的策略。在每一步做出当前看起来最好的选择（局部最优），然后求解剩下的子问题。做出选择后不需要回头。
2. 贪心选择性质是分水岭
贪心选择性质（Greedy-Choice Property）是指：可以通过做出局部最优（贪心）选择来产生全局最优解。
- 如果问题满足贪心选择性质，贪心算法和动态规划都能得到最优解，但贪心算法通常更高效
- 如果问题不满足贪心选择性质，贪心算法可能得到非最优解，此时必须使用动态规划
3. 经典问题分类
| 问题类型 | 动态规划 | 贪心算法 |
|---|---|---|
| 最长公共子序列 (LCS) | ✓ | ✗ |
| 0-1 背包问题 | ✓ | ✗ |
| 矩阵链乘法 | ✓ | ✗ |
| 活动选择问题 | ✓（也可用 DP） | ✓（更优） |
| Huffman 编码 | ✗ | ✓ |
| 最小生成树 | ✗ | ✓（Prim/Kruskal） |
| 单源最短路径（非负权） | ✓ | ✓（Dijkstra） |
| 分数背包问题 | ✗ | ✓ |
| 最优二叉搜索树 | ✓ | ✗ |
判断方法
判断一个问题能否用贪心算法求解，关键在于验证贪心选择性质：是否存在一种贪心策略，使得局部最优选择能导致全局最优？如果无法确定，优先考虑动态规划。
4. 设计范式对比
动态规划的设计步骤：
- 刻画最优解的结构特征（最优子结构）
- 递归定义最优解的值
- 计算最优解的值（通常自底向上填表）
- 构造最优解（回溯表格）
贪心算法的设计步骤：
- 将最优化问题转化为这样的形式：先做出选择，再求解一个子问题
- 证明问题具有贪心选择性质
- 证明最优子结构
- 设计递归贪心算法（可转化为迭代算法）
参见
- 14.3 动态规划设计要素 — 动态规划的设计方法与步骤
- 15.2 贪心策略要素 — 贪心算法的设计要素与证明方法
- 15.3 哈夫曼编码 — 贪心算法的经典应用