动态规划核心思想
动态规划解决什么问题？
- 思路: 把原问题分解为互相重叠的子问题, 存储子问题的解, 避免重复计算;
- dp 表: 存放子问题答案的数组;
- 前提: 子问题重叠是效率来源; 子问题不重叠时退化为普通分治或递归;
- 适用信号: 求最值、求方案数、判断是否存在, 且能按阶段递推;
fib(5) 的递归树中 fib(3)、fib(2) 被反复展开 -> 重叠子问题 -> 缓存结果即可降复杂度
什么是最优子结构？
- 定义: 原问题的最优解由子问题的最优解构建而来;
- 判据: 能写出
dp[大] = f(dp[小], ...), 且不需要保留子问题之外的信息; - 反例: 子问题的最优解拼不出原问题最优解时, 不能直接套用动态规划;
什么是无后效性？
- 定义: 状态确定后, 未来的演化只取决于当前状态, 与到达该状态的路径无关;
- 正例:
dp[i]只由dp[i-1]、dp[i-2]决定, 不关心前面怎么选的; - 反例: 后续决策依赖已走路径的细节 (例如必须记住完整访问集合), 需要扩维或更换状态定义;
- 后果: 后效性严重的问题很难用动态规划解决;
动态规划和其他方法如何区分？
| 方法 | 子问题关系 | 求解方向 | 典型场景 |
|---|---|---|---|
| 分治 | 互不重叠 | 自顶向下 | 归并排序 |
| 记忆化搜索 | 重叠, 递归 + 缓存 | 自顶向下 | 网格/图上的状态搜索 |
| 递推 dp | 重叠, 显式填表 | 自底向上 | 序列、矩阵、背包 |
| 贪心 | 每步取局部最优 | 一次扫描 | 区间调度 |