14.3.2 算法策略概述
四种策略之间最容易混的是分治、贪心和动态规划，因为它们都可能出现“子问题”和“最优”。辨析时要看子问题是否重叠、是否需要保存结果、局部选择是否能保证全局最优。
关键对比
| 策略 | 子问题关系 | 是否保存子问题解 | 是否一定求最优 |
|---|---|---|---|
| 分治 | 通常相互独立 | 不强调保存 | 不一定 |
| 贪心 | 每步做局部最优选择 | 不保存完整表 | 只有具备贪心性质时才全局最优 |
| 动态规划 | 子问题重叠 | 保存，常用数组/表 | 通常用于最优解 |
| 回溯 | 解空间分支 | 保存当前路径，失败回退 | 可求一个解或所有解 |
贪心与动态规划的共同点和差别
二者都可能要求最优解，也都可能提到最优子结构。
| 对比 | 贪心 | 动态规划 |
|---|---|---|
| 决策方式 | 当前一步直接选最优 | 综合多个子问题状态 |
| 是否反悔 | 通常不反悔 | 通过表格比较多个可能 |
| 典型题 | 最小生成树、哈夫曼树、Dijkstra | 背包、最长公共子序列、矩阵连乘 |
本节例题
关于算法策略，下列说法正确的是：
自查清单
- 能否解释贪心和动态规划都能求最优但方法不同？
- 能否判断子问题是否重叠？
- 能否把“解空间树”与回溯联系起来？