动态规划专题
算法动态规划DP
动态规划专题
📖 学习路径： 01 树遍历 → 02 DFS/BFS 进阶 → 03 动态规划
一、核心概念
1. 什么是动态规划
动态规划的核心：将大问题分解为重叠子问题，记录子问题的解，避免重复计算。
| 要素 | 含义 | 举例（斐波那契） |
|---|---|---|
| 最优子结构 | 大问题的最优解包含子问题的最优解 | F(n) = F(n-1) + F(n-2) |
| 重叠子问题 | 子问题被反复计算 | F(5) 依赖 F(4) 和 F(3)，F(4) 又依赖 F(3) |
| 无后效性 | 某阶段状态确定后，不受之后决策影响 | dp[i] 只依赖 dp[i-1] 和 dp[i-2] |
2. DP vs 回溯 vs 贪心
| 算法 | 特点 | 适用场景 |
|---|---|---|
| 回溯（DFS） | 穷举所有可能 | 需要所有解（全排列、子集） |
| 贪心 | 每步选局部最优 | 局部最优 = 全局最优 |
| DP | 记录子问题，自底向上 | 有重叠子问题，求最优解/方案数 |
3. DP 解题五步法
- 定义 dp 含义 —
dp[i]/dp[i][j]代表什么？ - 推导状态转移方程 — 当前状态如何由之前的状态得出？
- 确定初始条件/边界 —
dp[0]、dp[1]等特殊值 - 确定遍历顺序 — 正序？倒序？外层循环是谁？
- 举例推导验证 — 用小例子手动跑一遍
约定： 本专题所有代码使用统一风格。
- 变量名：一维用
dp，二维用dp，滚动变量用prev1/prev2- 先展示基础 DP 数组写法（方便理解），再给空间优化版（方便面试）
- 类型注解完整
二、代码框架（先基础写法，再优化）
框架一：一维线性 DP
核心： dp[i] 只依赖前面几个状态，正向递推。
const linearDP = (nums: number[]): number => {
const n = nums.length;
// ① 定义：dp[i] 表示...（根据题目确定）
const dp: number[] = new Array(n).fill(0);
// ② 初始化
dp[0] = nums[0];
// ③ 递推
for (let i = 1; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 1] + nums[i]); // 状态转移
}
// ④ 返回
return dp[n - 1];
};💡 优化：如果
dp[i]只依赖dp[i-1]和dp[i-2]，可以用两个变量替代整个数组（见例题）。
框架二：01 背包
核心： 每件物品只能选 0 或 1 次。dp[i][j] = 前 i 件物品，容量 j 时的最大价值。
const knapsack01 = (weights: number[], values: number[], capacity: number): number => {
const n = weights.length;
// ① 定义：dp[i][j] = 前 i 件物品，容量 j 时的最大价值
const dp: number[][] = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let j = 0; j <= capacity; j++) {
if (j < weights[i - 1]) {
// 装不下当前物品 → 只能不选
dp[i][j] = dp[i - 1][j];
} else {
// 装得下 → 选或不选取最大值
dp[i][j] = Math.max(
dp[i - 1][j], // 不选
dp[i - 1][j - weights[i - 1]] + values[i - 1] // 选
);
}
}
}
return dp[n][capacity];
};空间优化版（一维数组，倒序遍历）：
const knapsack01Optimized = (weights: number[], values: number[], capacity: number): number => {
const dp: number[] = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let j = capacity; j >= weights[i]; j--) { // ⚠️ 倒序！防止重复使用
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
};💡 为什么倒序？因为
dp[j - weights[i]]是上一轮（i-1）的值，如果正序会被本轮覆盖。
框架三：完全背包
核心： 每件物品可用无限次。与 01 背包的唯一区别：内层正序遍历。
const knapsackComplete = (weights: number[], values: number[], capacity: number): number => {
const dp: number[] = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let j = weights[i]; j <= capacity; j++) { // ⚠️ 正序！允许重复使用
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
};01背包 vs 完全背包对比：
| 01 背包 | 完全背包 | |
|---|---|---|
| 内层遍历 | j = capacity; j >= w; j--（倒序） |
j = w; j <= capacity; j++（正序） |
| 物品使用 | 每件最多 1 次 | 每件无限次 |
| 原因 | 倒序保证 dp[j-w] 是上一轮的值 |
正序允许本轮更新覆盖 |
框架四：二维网格 DP
核心： dp[i][j] 表示从起点到 (i,j) 的最优值，只能向右/向下移动。
const gridDP = (grid: number[][]): number => {
const m = grid.length, n = grid[0].length;
// ① 定义：dp[i][j] = 从 (0,0) 到 (i,j) 的最小路径和
const dp: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
// ② 初始化：起点 + 第一行 + 第一列
dp[0][0] = grid[0][0];
for (let j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
for (let i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
// ③ 递推：当前位置 = min(上, 左) + 当前格
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
};框架五：双串 DP（LCS 模板）
核心： dp[i][j] = 字符串 A 的前 i 个字符 与 字符串 B 的前 j 个字符 的关系。
const LCS = (text1: string, text2: string): number => {
const m = text1.length, n = text2.length;
// ① 定义：dp[i][j] = text1[0..i-1] 与 text2[0..j-1] 的 LCS 长度
const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
// ② 递推：遍历两个字符串
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1; // 字符相等：↖ + 1
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // 不等：max(←, ↑)
}
}
}
return dp[m][n];
};框架六：区间 DP
核心： dp[i][j] 表示区间 [i, j] 的状态，按区间长度递增遍历。
const intervalDP = (s: string): number => {
const n = s.length;
// dp[i][j] = 区间 [i, j] 是否为回文
const dp: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false));
// 初始化：单个字符
for (let i = 0; i < n; i++) dp[i][i] = true;
// 按长度递增遍历
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
if (s[i] === s[j]) {
dp[i][j] = len === 2 || dp[i + 1][j - 1];
}
}
}
return dp[0][n - 1]; // 或其他结果
};三、典型例题（由简到难）
🟢 线性 DP 入门
1. 爬楼梯（LeetCode 70）
问题： 每次爬 1 或 2 阶，爬到第 n 阶有多少种方法？
思路：
dp[i]= 爬到第i阶的方法数- 最后一步走 1 阶：
dp[i-1]；最后一步走 2 阶：dp[i-2] - 状态转移：
dp[i] = dp[i-1] + dp[i-2] - 初始：
dp[1] = 1,dp[2] = 2
基础版（DP 数组）：
const climbStairs = (n: number): number => {
if (n <= 2) return n;
const dp: number[] = new Array(n + 1);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};空间优化版（滚动变量）：
const climbStairsOptimized = (n: number): number => {
if (n <= 2) return n;
let prev2 = 1; // dp[i-2]
let prev1 = 2; // dp[i-1]
for (let i = 3; i <= n; i++) {
const cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
};💡
dp[i]只依赖dp[i-1]和dp[i-2]，所以两个变量就够了。
2. 斐波那契数（LeetCode 509）
问题： 计算
F(n)，其中F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。
// 基础版
const fib = (n: number): number => {
if (n <= 1) return n;
const dp: number[] = new Array(n + 1);
dp[0] = 0;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
// 空间优化版
const fibOptimized = (n: number): number => {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
const cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
};3. 使用最小花费爬楼梯（LeetCode 746）
问题： 每阶有花费
cost[i]，可从第 0 或第 1 阶开始，每次爬 1 或 2 阶，求到顶部的最小总花费。
思路：
dp[i]= 到达第i阶的最小花费- 可以从
i-1爬 1 阶：dp[i-1] + cost[i-1] - 可以从
i-2爬 2 阶：dp[i-2] + cost[i-2] - 状态转移：
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) - 初始：
dp[0] = 0, dp[1] = 0（起点不花费）
// 基础版
const minCostClimbingStairs = (cost: number[]): number => {
const n = cost.length;
const dp: number[] = new Array(n + 1);
dp[0] = 0; // 从第0阶开始，不花费
dp[1] = 0; // 从第1阶开始，不花费
for (let i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
};
// 空间优化版
const minCostClimbingStairsOptimized = (cost: number[]): number => {
const n = cost.length;
let prev2 = 0, prev1 = 0;
for (let i = 2; i <= n; i++) {
const cur = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
};4. 打家劫舍（LeetCode 198）
问题： 不能偷相邻的房屋，求能偷到的最大金额。
思路：
dp[i]= 偷到第i间时的最大金额- 偷当前：
dp[i-2] + nums[i] - 不偷当前：
dp[i-1] - 状态转移：
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
// 基础版
const rob = (nums: number[]): number => {
const n = nums.length;
if (n === 0) return 0;
if (n === 1) return nums[0];
const dp: number[] = new Array(n);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
};
// 空间优化版
const robOptimized = (nums: number[]): number => {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
let prev2 = nums[0];
let prev1 = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
const cur = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
};执行过程（nums=[2,7,9,3,1]）：
dp[0]=2 偷[2] → 2
dp[1]=7 偷[2,7] → max(2,7)=7
dp[2]=11 偷[2,7,9] → max(7, 2+9)=11
dp[3]=11 偷[2,7,9,3] → max(11, 7+3)=11
dp[4]=12 偷[2,7,9,3,1] → max(11, 11+1)=12
答案：12（偷 2→9→1 或 7→3→1）🟡 二维网格 DP
5. 不同路径（LeetCode 62）
问题：
m × n网格，从左上角到右下角，只能向右/向下，有多少条不同路径？
思路：
dp[i][j]= 从(0,0)到(i,j)的路径数- 只能从上方或左方来：
dp[i][j] = dp[i-1][j] + dp[i][j-1] - 第一行和第一列都只有 1 条路径
// 基础版（二维数组）
const uniquePaths = (m: number, n: number): number => {
const dp: number[][] = Array.from({ length: m }, () => new Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
};
// 空间优化版（一维数组）
const uniquePathsOptimized = (m: number, n: number): number => {
const dp: number[] = new Array(n).fill(1);
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1]; // dp[j] = 上方值, dp[j-1] = 左方值
}
}
return dp[n - 1];
};6. 最小路径和（LeetCode 64）
问题：
m × n非负网格，从左上到右下，只能向右/向下，求最小路径和。
思路：
dp[i][j]= 到(i,j)的最小路径和- 状态转移：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
// 基础版（二维数组）
const minPathSum = (grid: number[][]): number => {
const m = grid.length, n = grid[0].length;
const dp: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
// 初始化
dp[0][0] = grid[0][0];
for (let j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
for (let i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
// 递推
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
};
// 空间优化版（一维数组）
const minPathSumOptimized = (grid: number[][]): number => {
const m = grid.length, n = grid[0].length;
const dp: number[] = new Array(n);
dp[0] = grid[0][0];
for (let j = 1; j < n; j++) dp[j] = dp[j - 1] + grid[0][j];
for (let i = 1; i < m; i++) {
dp[0] += grid[i][0];
for (let j = 1; j < n; j++) {
dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
}
}
return dp[n - 1];
};执行过程（grid=[[1,3,1],[1,5,1],[4,2,1]]）：
网格： DP表：
1 3 1 1 4 5
1 5 1 → 2 7 6
4 2 1 6 8 7
↑ 答案=7
路径：1→3→1→1→1 = 7🟠 背包问题
7. 分割等和子集（LeetCode 416）— 01 背包
问题： 能否将数组分成两个和相等的子集？
转化： 能否选出一些数，和为 sum/2？→ 01 背包（布尔版）
const canPartition = (nums: number[]): boolean => {
const sum = nums.reduce((a, b) => a + b, 0);
if (sum % 2 !== 0) return false; // 奇数无法平分
const target = sum / 2;
// dp[j] = 能否选出和为 j 的子集
const dp: boolean[] = new Array(target + 1).fill(false);
dp[0] = true; // 和为 0 总是可以（不选任何数）
for (const num of nums) {
for (let j = target; j >= num; j--) { // 01背包 → 倒序
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
};执行过程（nums=[1,5,11,5], sum=22, target=11）：
初始化: dp[0]=true, 其余 false
处理 num=1:
j=11→1: dp[1]=true（选了1）
处理 num=5:
j=11→5: dp[6]=true（1+5）, dp[5]=true
处理 num=11:
j=11→11: dp[11]=true ✅ 找到！8. 零钱兑换（LeetCode 322）— 完全背包
问题： 每种硬币无限用，凑出
amount的最少硬币数。
思路： 完全背包（最小值版），正序遍历。
const coinChange = (coins: number[], amount: number): number => {
// dp[j] = 凑出金额 j 所需的最少硬币数
const dp: number[] = new Array(amount + 1).fill(Infinity);
dp[0] = 0; // 凑出 0 元需要 0 个硬币
for (const coin of coins) {
for (let j = coin; j <= amount; j++) { // 完全背包 → 正序
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
};执行过程（coins=[1,2,5], amount=11）：
初始化: dp[0]=0, 其余=∞
处理 coin=1（遍历 j=1→11）:
dp[1]=1, dp[2]=2, dp[3]=3, ..., dp[11]=11
处理 coin=2（遍历 j=2→11）:
dp[2]=min(2, dp[0]+1=1)=1
dp[3]=min(3, dp[1]+1=2)=2
...
处理 coin=5（遍历 j=5→11）:
dp[5]=min(5, dp[0]+1=1)=1
dp[6]=min(6, dp[1]+1=2)=2
...
dp[11]=min(11, dp[6]+1=3)=3
答案：3（5+5+1 或 5+2+2+2）9. 零钱兑换 II（LeetCode 518）— 组合数
问题： 每种硬币无限用，凑出
amount的组合数（顺序无关）。
思路： 完全背包（计数版）。⚠️ 外层遍历硬币保证是组合数，而非排列数。
const change = (amount: number, coins: number[]): number => {
// dp[j] = 凑出金额 j 的组合数
const dp: number[] = new Array(amount + 1).fill(0);
dp[0] = 1; // 凑出 0 元有 1 种方式（不选）
for (const coin of coins) { // 外层：硬币
for (let j = coin; j <= amount; j++) { // 内层：金额（正序）
dp[j] += dp[j - coin];
}
}
return dp[amount];
};💡 为什么外层是硬币？ 保证硬币按顺序使用（1→2→5），避免
[1,2]和[2,1]被重复计数。
🔴 子序列 DP
10. 最长递增子序列 LIS（LeetCode 300）
问题： 求数组中最长严格递增子序列的长度（不要求连续）。
思路：
dp[i]= 以nums[i]结尾的最长递增子序列长度- 对于每个
j < i，如果nums[i] > nums[j]，则可以接在j后面 - 状态转移：
dp[i] = max(dp[j] + 1)对所有满足条件的j
const lengthOfLIS = (nums: number[]): number => {
const n = nums.length;
// dp[i] = 以 nums[i] 结尾的 LIS 长度
const dp: number[] = new Array(n).fill(1); // 每个元素自身长度为1
let maxLen = 1;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
};执行过程（nums=[10,9,2,5,3,7,101,18]）：
i=0: nums[0]=10, dp[0]=1
i=1: nums[1]=9, 9<10 → dp[1]=1
i=2: nums[2]=2, 2<9,2<10 → dp[2]=1
i=3: nums[3]=5, 5>2 → dp[3]=dp[2]+1=2
i=4: nums[4]=3, 3>2 → dp[4]=dp[2]+1=2
i=5: nums[5]=7, 7>2→2, 7>5→3, 7>3→3 → dp[5]=3
i=6: nums[6]=101, 101>all → dp[6]=max(dp[0..5])+1=4
i=7: nums[7]=18, 18>... → dp[7]=max(dp[0..6]中<18的)+1=4
答案：4（子序列 [2,5,7,101] 或 [2,3,7,101]）11. 最长公共子序列 LCS（LeetCode 1143）
问题： 求两个字符串的最长公共子序列长度（不要求连续，保持原顺序）。
思路：
dp[i][j]=text1[0..i-1]与text2[0..j-1]的 LCS 长度- 字符相等：
dp[i][j] = dp[i-1][j-1] + 1（↖ + 1） - 字符不等：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])（← 或 ↑ 取最大）
const longestCommonSubsequence = (text1: string, text2: string): number => {
const m = text1.length, n = text2.length;
const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1; // 字符相等：↖ + 1
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // 不等：取最大
}
}
}
return dp[m][n];
};DP 表演示（text1=“abcde”, text2=“ace”）：
"" a c e
"" 0 0 0 0
a 0 1 1 1 ← a==a: 1+0=1
b 0 1 1 1 ← b≠a,b≠c,b≠e → max(1,1)=1
c 0 1 2 2 ← c==c: 1+1=2
d 0 1 2 2
e 0 1 2 3 ← e==e: 1+2=3
↑ 答案=3 (子序列 "ace")12. 最长回文子串（LeetCode 5）
问题： 求字符串中最长的回文子串。
思路： 区间 DP。dp[i][j] = s[i..j] 是否为回文。
- 按子串长度递增遍历
s[i]==s[j]且 (len==2或dp[i+1][j-1]==true)
const longestPalindrome = (s: string): string => {
const n = s.length;
// dp[i][j] = s[i..j] 是否为回文
const dp: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false));
let start = 0, maxLen = 1;
// 初始化：所有单个字符都是回文
for (let i = 0; i < n; i++) {
dp[i][i] = true;
}
// 按子串长度递增遍历
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
if (s[i] === s[j]) {
if (len === 2) {
dp[i][j] = true; // 两个相同字符 → 回文
} else {
dp[i][j] = dp[i + 1][j - 1]; // 依赖内部子串
}
}
if (dp[i][j] && len > maxLen) {
start = i;
maxLen = len;
}
}
}
return s.substring(start, start + maxLen);
};执行过程（s=“babad”）：
len=1: b,a,b,a,d → 全部 true
len=2: ba(false), ab(false), ba(false), ad(false) → 无
len=3: bab: s[0]=s[2]='b' && dp[1][1]=true → true ✅ (len=3)
aba: s[1]=s[3]='a' && dp[2][2]=true → true ✅ (len=3)
len=4: baba: s[0]=s[3]='a'='a'? → s[0]='b'≠'a' → false
len=5: babad: s[0]='b'≠'d' → false
答案："bab"（或 "aba"）13. 编辑距离（LeetCode 72）
问题： 求将
word1转换为word2的最少操作数（插入、删除、替换各算 1 次）。
思路：
dp[i][j]=word1[0..i-1]转换为word2[0..j-1]的最小操作数- 字符相等：
dp[i][j] = dp[i-1][j-1]（无需操作） - 字符不等：三种操作取最小 + 1
- 删除
word1[i-1]：dp[i-1][j] + 1 - 插入
word2[j-1]：dp[i][j-1] + 1 - 替换：
dp[i-1][j-1] + 1
- 删除
const minDistance = (word1: string, word2: string): number => {
const m = word1.length, n = word2.length;
// dp[i][j] = word1[0..i-1] → word2[0..j-1] 的最少操作数
const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
// 初始化：空字符串转换的边界
for (let i = 0; i <= m; i++) dp[i][0] = i; // 删除 i 次
for (let j = 0; j <= n; j++) dp[0][j] = j; // 插入 j 次
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // 相等，无需操作
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j], // 删除 word1[i-1]
dp[i][j - 1], // 插入 word2[j-1]
dp[i - 1][j - 1] // 替换
);
}
}
}
return dp[m][n];
};执行过程（word1=“horse”, word2=“ros”）：
"" r o s
"" 0 1 2 3
h 1 1 2 3 ← h≠r → min(删h, 插r, 替h→r)=1
o 2 2 1 2 ← o==o → dp[1][1]=1
r 3 2 2 2 ← r==r → dp[2][1]=2
s 4 3 3 2 ← s≠o → min(删,插,替)=2
e 5 4 4 3 ← e≠s → min=3
↑ 答案=3
操作：horse → rorse(替h→r) → rose(删r) → ros(删e)四、总结
题目速查表
| # | 题目 | DP 类型 | 状态转移 |
|---|---|---|---|
| 1 | 爬楼梯 | 线性 DP | dp[i] = dp[i-1] + dp[i-2] |
| 2 | 斐波那契 | 线性 DP | dp[i] = dp[i-1] + dp[i-2] |
| 3 | 最小花费爬楼梯 | 线性 DP | dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]) |
| 4 | 打家劫舍 | 线性 DP | dp[i] = max(dp[i-1], dp[i-2]+nums[i]) |
| 5 | 不同路径 | 二维网格 DP | dp[i][j] = dp[i-1][j] + dp[i][j-1] |
| 6 | 最小路径和 | 二维网格 DP | dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] |
| 7 | 分割等和子集 | 01 背包 | dp[j] = dp[j] || dp[j-num]（倒序） |
| 8 | 零钱兑换 | 完全背包 | dp[j] = min(dp[j], dp[j-coin]+1)（正序） |
| 9 | 零钱兑换 II | 完全背包 | dp[j] += dp[j-coin]（正序，外层硬币） |
| 10 | 最长递增子序列 | 子序列 DP | dp[i] = max(dp[j]+1)（对所有 j<i, nums[j]<nums[i]） |
| 11 | 最长公共子序列 | 双串 DP | dp[i][j] = (相等?↖+1 : max(←,↑)) |
| 12 | 最长回文子串 | 区间 DP | dp[i][j] = s[i]==s[j] && dp[i+1][j-1] |
| 13 | 编辑距离 | 双串 DP | dp[i][j] = min(删,插,替) + 1 |
统一框架回顾
| DP 类型 | 特征 | 遍历方式 |
|---|---|---|
| 线性 DP | dp[i] 依赖前几个 |
正向遍历 |
| 01 背包 | 每件最多 1 次 | 外层物品，内层容量倒序 |
| 完全背包 | 每件无限次 | 外层物品，内层容量正序 |
| 二维网格 | dp[i][j]，只向右/下 |
i 从 0→m, j 从 0→n |
| 双串 DP | 两个字符串/数组 | 双层循环，i+1 行 j+1 列 |
| 区间 DP | dp[i][j] 表示区间 |
按区间长度递增遍历 |
背包问题速记
| 01 背包 | 完全背包 | |
|---|---|---|
| 内层遍历 | for (j=cap; j>=w; j--) |
for (j=w; j<=cap; j++) |
| 核心公式 | dp[j] = max(dp[j], dp[j-w] + v) |
同左，但正序 |
| 求组合数 | 外层物品，内层金额 | 外层物品，内层金额 |
| 求排列数 | — | 外层金额，内层物品 |
记忆口诀
- 线性递推：看前两三个状态
- 01 背包倒着走，完全背包正着走
- 二维网格：上 + 左，取 min/max + 当前
- 双串 DP：相等 ↖+1，不等 max(←,↑)
- 区间 DP：按长度递增，
dp[i][j]依赖dp[i+1][j-1] - 组合外层是物品，排列外层是金额
关联题库
以下题目与本文知识点相关，可以跳转到题库练习：