动态规划框架
raw/articles/2026/05/动态规划框架.md
一句话总结
本文系统讲解动态规划的核心思想、三要素（重叠子问题、最优子结构、状态转移方程）及通用解题框架，通过斐波那契数列和零钱兑换两个经典问题演示从暴力递归到优化解法的完整过程。
核心要点
1. 动态规划三要素
- 重叠子问题：递归过程中子问题被重复计算，导致时间复杂度指数级增长，可通过「备忘录」或「DP table」优化
- 最优子结构：子问题之间互相独立，原问题的最值可以通过子问题的最值推导得出
- 状态转移方程：描述状态之间转移关系的数学形式，是动态规划问题的核心，列出方程是解题关键
2. 通用解题框架
按以下三步思考：
- 明确「状态」：原问题和子问题中变化的变量
- 明确「选择」：导致状态产生变化的行为
- 定义
dp数组/函数的含义
对应两种实现形式：
- 自顶向下：带备忘录的递归解法
- 自底向上：DP table 迭代解法
3. 优化技巧
- 空间压缩：当状态转移仅依赖前几个状态时，可以缩小 DP table 的规模（例如斐波那契数列从 O(n) 空间压缩到 O(1)）
基本原理
动态规划的核心思想是穷举求最值，通过备忘录或 DP table 消除重叠子问题，利用最优子结构通过子问题推导原问题。
状态转移方程示例（零钱兑换问题）： $$ dp(n) = \begin{cases} 0, & n = 0 \ -1, & n < 0 \ \min{dp(n - \text{coin}) + 1 | \text{coin} \in \text{coins}}, & n > 0 \end{cases} $$
| 概念 | 说明 |
|---|---|
| 重叠子问题 | 递归过程中重复计算的子问题，是动态规划问题的时间杀手 |
| 最优子结构 | 子问题互相独立，原问题最值可由子问题最值推导 |
| 状态转移方程 | 描述状态间转移关系的数学形式，是动态规划的核心 |
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 斐波那契数列暴力递归 | O(2^n) | 递归树节点数为 2^n，每个子问题计算时间 O(1) |
| 斐波那契数列带备忘录/DP table | O(n) | 子问题数为 O(n)，每个子问题计算时间 O(1) |
| 零钱兑换暴力递归 | O(k^n) | k 为硬币种类数，最坏情况为满 k 叉树 |
| 零钱兑换带备忘录/DP table | O(kn) | 子问题数为 O(n)，每个子问题需要遍历 k 种硬币 |
代码实现
斐波那契数列（DP table 迭代解法）
int fib(int n) {
if (n == 0 || n == 1) {
return n;
}
int[] dp = new int[n + 1];
// base case
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 table 迭代解法）
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 初始化为一个不可能取到的大值（amount + 1 相当于正无穷）
Arrays.fill(dp, amount + 1);
// base case
dp[0] = 0;
// 外层遍历所有状态
for (int i = 0; i < dp.length; i++) {
// 内层遍历所有选择，求最小值
for (int coin : coins) {
if (i - coin < 0) {
continue;
}
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
}
实现要点
- 备忘录/DP table 初始化：用一个不可能取到的值表示未计算状态（如 -1、amount + 1）
- base case 处理：递归解法先判断 base case，迭代解法先初始化 dp[0]
- 空间压缩：当状态仅依赖前几个状态时，可缩小 DP 数组规模（如斐波那契用两个变量代替数组）
相关题目
| 平台 | 题目 | 难度 |
|---|---|---|
| LeetCode | 509. 斐波那契数 | 简单 |
| LeetCode | 70. 爬楼梯 | 简单 |
| LeetCode | 322. 零钱兑换 | 中等 |
相关概念
- 动态规划：本文核心主题
- 重叠子问题：动态规划三要素之一
- 最优子结构：动态规划三要素之一
- 状态转移方程：动态规划核心
- 递归：本文用递归作为基础讲解工具
- 备忘录：优化重叠子问题的方法
- DP table：迭代式动态规划的实现形式
总结
动态规划的本质是穷举求最值，核心是列出正确的状态转移方程，通过备忘录或 DP table 消除重叠子问题，利用最优子结构推导原问题。通用解题框架为：明确状态 → 明确选择 → 定义 dp 数组/函数，大部分问题可通过此框架系统解决。