什么是动态规划 动态规划（Dynamic Programming，简称 DP） 是一种通过将原问题分解为若干重叠子问题，并存储子问题的解以避免重复计算，从而高效求解最优化问题的算法思想。
动态规划的核心在于 「记住求过的解」 —— 用空间换时间。
flowchart LR A[原问题] --> B[子问题 1] A --> C[子问题 2] A --> D[子问题 n] B --> E((存储)) C --> E D --> E E --> F[组合子问题解] F --> G[得到原问题最优解] style E fill:#f96,stroke:#333,stroke-width:2px
适用条件 一个问题能用动态规划求解，需要满足两个关键性质：
性质
说明
反例
最优子结构 原问题的最优解包含子问题的最优解
无权最长简单路径（NP-hard）
重叠子问题 子问题被反复求解，而非每次独立
二分查找（子问题不重叠）
💡 如果子问题不重叠，用分治法即可（如归并排序）；只有子问题重叠 时，DP 才比分治更有优势。
动态规划的解题步骤 解决 DP 问题通常遵循一个固定的思维框架：
flowchart TD A[1. 定义状态] --> B[2. 确定状态转移方程] B --> C[3. 初始化边界条件] C --> D[4. 确定遍历顺序] D --> E[5. 返回最终结果] A -.-> A1["dp[i] 或 dp[i][j] 表示什么"] B -.-> B1["dp[i] = f(dp[i-1], dp[i-2], ...)"] C -.-> C1["dp[0], dp[1] 等初始值"] D -.-> D1["从左到右 / 从上到下"] E -.-> E1["返回 dp[n] 或 dp[m][n]"] style A1 fill:#e8f4fd,stroke:#4a90d9 style B1 fill:#e8f4fd,stroke:#4a90d9 style C1 fill:#e8f4fd,stroke:#4a90d9 style D1 fill:#e8f4fd,stroke:#4a90d9 style E1 fill:#e8f4fd,stroke:#4a90d9
下面通过三个递进的例题来掌握这些步骤。
例题一：斐波那契数列（入门） 问题 计算斐波那契数列的第 n 项：
F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2)（n ≥ 2）
递归 vs DP（为什么需要 DP？） flowchart TD subgraph 递归树 F5[F5] --> F4[F4] F5 --> F3a[F3] F4 --> F3b[F3] F4 --> F2a[F2] F3a --> F2b[F2] F3a --> F1a[F1] F3b --> F2c[F2] F3b --> F1b[F1] F2a --> F1c[F1] F2a --> F0a[F0] F2b --> F1d[F1] F2b --> F0b[F0] F2c --> F1e[F1] F2c --> F0c[F0] end style F3a fill:#fdd,stroke:#e74c3c style F3b fill:#fdd,stroke:#e74c3c style F2a fill:#fdd,stroke:#e74c3c style F2b fill:#fdd,stroke:#e74c3c style F2c fill:#fdd,stroke:#e74c3c
纯递归计算 F(5) 时，F(3) 被计算 2 次、F(2) 被计算 3 次——大量重复！
DP 解法： 用一个数组把算过的值存起来，遇到直接取，不再重复计算。
状态定义与转移
状态定义： dp[i] 表示斐波那契数列第 i 项的值状态转移方程： dp[i] = dp[i-1] + dp[i-2]边界条件： dp[0] = 0, dp[1] = 1遍历顺序： 从左到右
代码实现 public class Fibonacci { public static int fibRecursive (int n) { if (n <= 1 ) return n; return fibRecursive(n - 1 ) + fibRecursive(n - 2 ); } public static int fibDP (int n) { if (n <= 1 ) 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]; } public static int fibOptimized (int n) { if (n <= 1 ) return n; int prev2 = 0 , prev1 = 1 ; for (int i = 2 ; i <= n; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; } return prev1; } }
复杂度分析
方法
时间复杂度
空间复杂度
纯递归
O(2ⁿ)
O(n)（调用栈）
DP 数组
O(n)
O(n)
DP 空间优化
O(n)
O(1)
例题二：0-1 背包问题（经典） 问题 给定 n 件物品和一个容量为 C 的背包。每件物品 i 有重量 w[i] 和价值 v[i]。每件物品只能选一次（0 或 1 次）， 求不超过背包容量的前提下能装的最大总价值。
物品
重量
价值
A
2
3
B
3
4
C
4
5
D
5
6
背包容量 C = 8
决策过程 flowchart TD subgraph 对每件物品做决策 direction LR S[物品 i] --> Choice{选 or 不选?} Choice -->|不选| Skip["dp[i][j] = dp[i-1][j]<br/>继承上一行的结果"] Choice -->|选| Take["dp[i][j] = dp[i-1][j-w[i]] + v[i]<br/>腾出重量再放"] end
状态定义与转移
状态定义： dp[i][j] 表示前 i 件物品中选，容量为 j 的背包能装的最大价值状态转移方程：
dp[i] [j] = max ( dp[i-1] [j] , ← 不选第 i 件 dp[i-1] [j-w[i] ] + v[i] ← 选第 i 件（前提：j ≥ w[i] ） )
边界条件： dp[0][j] = 0 且 dp[i][0] = 0遍历顺序： 先遍历物品，再遍历容量
DP 表格演算 容量 j → 0 1 2 3 4 5 6 7 8 物品 ↓ ┌───────────────────────────────── 0 │ 0 0 0 0 0 0 0 0 0 A(w=2) │ 0 0 3 3 3 3 3 3 3 B(w=3) │ 0 0 3 4 4 7 7 7 7 C(w=4) │ 0 0 3 4 5 7 8 9 9 D(w=5) │ 0 0 3 4 5 7 8 9 9 ← 最大价值 9
红色箭头表示做出「选」决策的位置：
flowchart LR subgraph 最优解回溯 D4["D(w=5,v=6) 不选<br/>j=8 不变"] --> C4["C(w=4,v=5) 选 ✓<br/>容量 -> 8-4=4"] C4 --> B4["B(w=3,v=4) 不选<br/>j=4 不变"] B4 --> A4["A(w=2,v=3) 选 ✓<br/>容量 -> 4-2=2"] A4 --> END["剩余容量 2，结束"] end style C4 fill:#cfc,stroke:#27ae60 style A4 fill:#cfc,stroke:#27ae60
最优解： 选 A + C，总重量 2 + 4 = 6 ≤ 8，总价值 3 + 5 = 9
代码实现 public class Knapsack01 { public static int knapsack (int C, int [] w, int [] v) { int n = w.length; int [][] dp = new int [n + 1 ][C + 1 ]; for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= C; j++) { dp[i][j] = dp[i - 1 ][j]; if (j >= w[i - 1 ]) { dp[i][j] = Math.max(dp[i][j], dp[i - 1 ][j - w[i - 1 ]] + v[i - 1 ]); } } } return dp[n][C]; } public static int knapsackOptimized (int C, int [] w, int [] v) { int n = w.length; int [] dp = new int [C + 1 ]; for (int i = 0 ; i < n; i++) { for (int j = C; j >= w[i]; j--) { dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]); } } return dp[C]; } }
⚠️ 为什么一维优化要逆序遍历容量？ dp[j-w[i]] 读取的是上一轮（未选当前物品）的值，如果正序就会读到本轮已经更新过的「选了一次」的值，变成完全背包问题了。
复杂度分析
维度
二维 DP
一维优化
时间复杂度
O(n×C)
O(n×C)
空间复杂度
O(n×C)
O(C)
例题三：最长公共子序列（进阶） 问题 给定两个字符串 text1 和 text2，返回它们的最长公共子序列（LCS）的长度。
子序列： 不要求连续，但相对顺序不变。
text1 = “abcde”, text2 = “ace” → LCS = “ace”（长度 3）
text1 = “abc”, text2 = “def” → LCS = “”（长度 0）
决策分析 flowchart TD subgraph 比较 s1[i] 和 s2[j] direction LR CMP[字符相等?] -->|Yes| MATCH["dp[i][j] = dp[i-1][j-1] + 1<br/>匹配上，各退一步 +1"] CMP -->|No| SKIPA["方案A: 跳过 s1[i]<br/>dp[i-1][j]"] CMP -->|No| SKIPB["方案B: 跳过 s2[j]<br/>dp[i][j-1]"] SKIPA --> MAX["取较大值"] SKIPB --> MAX end
状态定义与转移
状态定义： dp[i][j] 表示 text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度状态转移方程：
if text1[i-1] == text2[j-1] : dp[i] [j] = dp[i-1] [j-1] + 1 ← 字符匹配 else : dp[i] [j] = max (dp[i-1] [j] , dp[i] [j-1] ) ← 不匹配，取较大子问题
边界条件： dp[0][j] = 0 且 dp[i][0] = 0遍历顺序： 从左到右、从上到下
DP 表格演算 text1 = "abcde", text2 = "ace" "" a c e "" 0 0 0 0 a 0 1 1 1 ← a 匹配 b 0 1 1 1 c 0 1 2 2 ← c 匹配 d 0 1 2 2 e 0 1 2 3 ← e 匹配 → 答案 3
代码实现 public class LCS { public static int longestCommonSubsequence (String text1, String text2) { int m = text1.length(), n = text2.length(); int [][] dp = new int [m + 1 ][n + 1 ]; for (int i = 1 ; i <= m; i++) { for (int j = 1 ; j <= n; j++) { if (text1.charAt(i - 1 ) == text2.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; } else { dp[i][j] = Math.max(dp[i - 1 ][j], dp[i][j - 1 ]); } } } return dp[m][n]; } public static String getLCS (String text1, String text2) { int m = text1.length(), n = text2.length(); int [][] dp = new int [m + 1 ][n + 1 ]; for (int i = 1 ; i <= m; i++) { for (int j = 1 ; j <= n; j++) { if (text1.charAt(i - 1 ) == text2.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; } else { dp[i][j] = Math.max(dp[i - 1 ][j], dp[i][j - 1 ]); } } } StringBuilder sb = new StringBuilder (); int i = m, j = n; while (i > 0 && j > 0 ) { if (text1.charAt(i - 1 ) == text2.charAt(j - 1 )) { sb.append(text1.charAt(i - 1 )); i--; j--; } else if (dp[i - 1 ][j] > dp[i][j - 1 ]) { i--; } else { j--; } } return sb.reverse().toString(); } }
复杂度分析
维度
值
时间复杂度
O(m × n)
空间复杂度
O(m × n)（可优化至 O(min(m, n))）
动态规划解题套路总结 flowchart TB Start[拿到问题] --> Q1{是否求最值?} Q1 -->|是| Q2{能分解为子问题?} Q2 -->|是| Q3{子问题重叠?} Q3 -->|是| DP[用 DP 求解] Q3 -->|否| DIV[用分治法] Q2 -->|否| GREEDY[试试贪心] DP --> STEP1[定义 dp 数组含义] STEP1 --> STEP2[写转移方程] STEP2 --> STEP3[确定边界] STEP3 --> STEP4[确定遍历顺序] STEP4 --> DONE[输出结果] style DP fill:#4a90d9,color:#fff style DONE fill:#27ae60,color:#fff
常见 DP 题型速查
类型
状态定义特征
典型题
线性 DP dp[i] 与前 i 项有关斐波那契、爬楼梯、最大子数组和
区间 DP dp[i][j] 表示区间 [i, j]最长回文子串、石子合并
背包 DP dp[i][j] 前 i 件物品容量 j0-1 背包、完全背包、多重背包
树形 DP dp[node] 以 node 为根的子树打家劫舍 III、树的最大独立集
数位 DP dp[pos][state] 在数位上做 DP数字 1 的个数、不包含 49 的数字
刷题推荐顺序
爬楼梯 → dp[i] = dp[i-1] + dp[i-2]（入门）打家劫舍 → dp[i] = max(dp[i-1], dp[i-2] + nums[i])最大子数组和 → dp[i] = max(nums[i], dp[i-1] + nums[i])0-1 背包 → 二维 DP 表格理解透彻最长递增子序列 → O(n²) 入门 → O(n log n) 进阶最长公共子序列 → 两个维度的 DP 训练编辑距离 → LCS 的进阶版完全平方数 → 背包思想的变体
总结 动态规划的难点不在于代码实现，而在于 识别问题类型 和 定义合适的状态 。掌握了状态定义和转移方程，代码往往只有几行。
关键记忆：
✅ 最优子结构 + 重叠子问题 = DP
✅ 状态定义是 DP 的灵魂，转移方程是骨架
✅ 先二维理解，再一维优化（不要一上来就优化）
✅ 多画 DP 表格，演算两三组数据就能发现规律
多刷题，形成「状态直觉」 —— 看到题目就知道该用一维还是二维 DP
flowchart LR subgraph 学习路径 FIB[斐波那契<br/>入门] --> HOUSE[打家劫舍<br/>简单一维] HOUSE --> KNAPSACK[0-1 背包<br/>二维经典] KNAPSACK --> LCS["LCS/LIS<br/>序列DP"] LCS --> EDIT[编辑距离<br/>二维进阶] EDIT --> TREE[树形DP<br/>高阶] end style FIB fill:#e8f4fd,stroke:#4a90d9 style HOUSE fill:#e8f4fd,stroke:#4a90d9 style KNAPSACK fill:#d4edda,stroke:#27ae60 style LCS fill:#d4edda,stroke:#27ae60 style EDIT fill:#fce4ec,stroke:#e74c3c style TREE fill:#fce4ec,stroke:#e74c3c