动态规划
将复杂问题分解为重叠子问题，通过存储中间结果避免重复计算，自底向上求解。
核心特征
- 最优子结构：最优解包含子问题最优解
- 重叠子问题：不同路径遇到相同子问题（区别于分治）
- 无后效性：决策仅依赖当前状态
解题步骤
- 定义状态：确定 dp 数组的含义和维度
- 建立状态转移方程：写出递推关系
- 确定边界：初始化基础情况
- 确定遍历顺序：保证计算当前状态时所需子状态已算出
经典问题
| 类型 | 问题 |
|---|---|
| 线性 DP | 爬楼梯、打家劫舍 |
| 背包 DP | 0-1 背包、完全背包 |
| 区间 DP | 最长回文子串、矩阵链乘法 |
| 树形 DP | 二叉树最大路径和 |
| 状态压缩 DP | 旅行商问题（TSP） |
空间优化
观察转移方程仅依赖有限个前序状态时，可用滚动变量将 空间降为 。