动态规划（Dynamic Programming）
动态规划是「分解问题」思维模式的延伸，通过把问题分解为子问题、记忆化子问题答案，从而避免重复计算，优化递归效率。
定义
动态规划（Dynamic Programming，DP）是一种算法设计思想，通过将复杂问题分解为重叠的子问题，并存储子问题的解来避免重复计算，从而得到原问题的最优解。
核心本质：动态规划 = 递归（分解问题） + 记忆化（避免重复计算）
核心特性
| 特性 | 说明 |
|---|---|
| 重叠子问题 | 子问题会被重复计算多次 |
| 最优子结构 | 原问题的最优解包含子问题的最优解 |
| 状态转移 | 通过已解决的子问题推导当前问题 |
| 自底向上/自顶向下 | 两种实现方向 |
与递归的关系
动态规划与递归（分解问题思维）的关系：
| 维度 | 普通递归 | 动态规划 |
|---|---|---|
| 思维模式 | 分解问题 | 分解问题 + 记忆化 |
| 子问题处理 | 可能重复计算 | 存储子问题解，避免重复 |
| 效率 | 可能指数级 | 通常多项式级 |
| 示例 | 斐波那契递归 | 斐波那契带记忆化 |
关键洞察：理解递归是学习动态规划的前提。从树的角度理解递归，就更容易理解动态规划的状态转移。
与贪心算法的区别
动态规划与贪心算法都用于优化问题，但核心思路不同（参见 贪心算法解题套路框架）：
| 维度 | 动态规划 | 贪心算法 |
|---|---|---|
| 穷举范围 | 穷举所有可行解（去重后） | 不穷举所有可行解 |
| 优化手段 | 备忘录优化，避免重复计算 | 推导最优，直接选择局部最优解 |
| 适用条件 | 最优子结构 + 重叠子问题 | 最优子结构 + 贪心选择性质 |
| 时间复杂度 | 多项式级 $O(n^2)$ 等 | 通常 $O(n)$ 或 $O(1)$ |
| 正确性 | 只要满足最优子结构就正确 | 需要证明贪心选择性质成立 |
关键区别：动态规划仍然穷举所有可行解（只是去掉重复计算），而贪心算法直接跳过完整穷举，通过局部最优选择推导全局最优。
两种实现方式
1. 自顶向下（Top-Down）
特点：从原问题出发，递归求解子问题，用备忘录存储结果
示例（斐波那契带记忆化）：
int fib(int n, Map<Integer, Integer> memo) {
if (n < 2) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = fib(n-1, memo) + fib(n-2, memo);
memo.put(n, result);
return result;
}
2. 自底向上（Bottom-Up）
特点：从最小的子问题开始，迭代计算更大问题的解
示例（斐波那契）：
int fib(int n) {
if (n < 2) return n;
int[] dp = new int[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
动态规划三要素
- 状态定义：dp[i] 或 dp[i][j] 表示什么
- 状态转移方程：如何由子问题推导当前问题
- 边界条件：最小的子问题如何求解
常见类型
| 类型 | 说明 | 经典问题 |
|---|---|---|
| 线性 DP | 状态是线性序列 | 最长递增子序列、最大子数组和 |
| 区间 DP | 状态是区间 [i, j] | 矩阵链乘法、最长回文子串 |
| 背包 DP | 状态包含容量和物品 | 0-1 背包、完全背包 |
| 树形 DP | 状态在树节点上 | 二叉树最大路径和 |
| 状压 DP | 状态用二进制压缩 | 旅行商问题（TSP） |
经典算法
| 算法/问题 | 难度 | 说明 |
|---|---|---|
| 斐波那契数列（带记忆化） | 简单 | 入门 DP，理解重叠子问题 |
| 0-1 背包问题 | 中等 | 经典 DP，理解状态和选择 |
| 最长公共子序列（LCS） | 中等 | 二维 DP 经典问题 |
| 最长递增子序列（LIS） | 中等 | 线性 DP |
| 最大子数组和（Kadane） | 简单 | 线性 DP，状态压缩 |
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 自顶向下（带记忆化） | O(状态数) | 每个状态只计算一次 |
| 自底向上 | O(状态数 × 转移复杂度) | 迭代计算所有状态 |
| 空间复杂度 | O(状态数) | 存储所有子问题解 |
注意事项
- 状态定义要清晰：dp 数组的含义必须明确
- 边界条件不能漏：最小的子问题必须正确初始化
- 遍历顺序要正确：自底向上时要注意计算顺序
- 空间可以优化：有时可以只用一维数组或几个变量
应用场景
- 最优化问题：求最大值、最小值、最长、最短等
- 计数问题：有多少种方式、方案数等
- 存在性问题：是否能达到某个状态
- 路径规划：最短路径、最小代价等
相关概念
- 递归：动态规划的基础，分解问题思维
- 分治算法：也分解问题，但子问题不重叠
- 回溯算法：遍历思维，通常不考虑优化
- 贪心算法：比动态规划更进一步，不穷举所有可行解
- 斐波那契数列：DP 入门经典例子
- 二叉树：树形 DP 的应用场景