元数据卡
- 前置知识：ch13-dp-intro（重叠子问题、记忆化）
- 预计时间：30 分钟
- 核心难度：进阶
- 完成标志：能独立写出 0-1 背包、LCS、编辑距离的 DP 解法
你的进度
上一章你学会了斐波那契——DP 的"Hello World"。现在驿站长老拿来任务清单：背包里装哪些物资价值最高、两条林间日志的最长共同记录是什么。
你的任务 掌握三个经典二维 DP 模型：0-1 背包（选择问题）、LCS（顺序匹配）、编辑距离（序列转换）。学会后你会发现 80% 的面试 DP 题是它们的变体。
0-1 背包
N 个物品，每个有重量 w[i] 和价值 v[i]，背包容量 W。每个物品拿 0 或 1 个。
状态： dp[i][w] = 前 i 个物品在容量 w 下的最大价值。
python
def knapsack_01(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
print(knapsack_01([2,3,4,5], [3,4,5,6], 8))
# 预期: 10 (选物品 3+4 价值 5+5)java
public class Knapsack {
public static int knapsack01(int[] w, int[] v, int W) {
int n = w.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++)
for (int c = 0; c <= W; c++)
if (w[i-1] <= c)
dp[i][c] = Math.max(dp[i-1][c], dp[i-1][c-w[i-1]] + v[i-1]);
else
dp[i][c] = dp[i-1][c];
return dp[n][W];
}
public static void main(String[] args) {
System.out.println(knapsack01(new int[]{2,3,4,5}, new int[]{3,4,5,6}, 8));
}
}
// 运行: java Knapsack 预期: 10空间优化到一维： 反向遍历，确保每个物品只用一次。
python
def knapsack_01_opt(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
print(knapsack_01_opt([2,3,4,5], [3,4,5,6], 8)) # 10完全背包正向遍历，因为物品可以无限取。口诀：0-1 反向，完全正向。
最长公共子序列（LCS）
给定两个字符串，求最长公共子序列长度（不要求连续，顺序必须一致）。
状态： dp[i][j] = text1 前 i 字符和 text2 前 j 字符的 LCS 长度。
转移： 字符相等则 dp[i-1][j-1]+1，否则取 max(dp[i-1][j], dp[i][j-1])。
python
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
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])
return dp[m][n]
print(lcs("abcde", "ace"))
# 预期: 3 ("ace")编辑距离
每次可插入、删除、替换一个字符，求最少操作次数。
python
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i
for j in range(n + 1): dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]
print(min_distance("horse", "ros"))
# 预期: 3 (horse->rorse->rose->ros)状态定义模板——通用框架
- 定义 dp 维度：一维 -> 一个序列；二维 -> 两个序列
- 边界条件：dp[0][] 和 dp[][0] 是什么
- 转移方程：dp[i][j] 依赖 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 中的哪些
- 遍历顺序：通常从左上到右下
- 答案位置：dp[m][n] 或 max(dp[*])
经典序列 DP 对比：
| 问题 | 状态定义 | 转移 | 维度 |
|---|---|---|---|
| 斐波那契 | dp[i] = 第 i 个数 | dp[i] = dp[i-1]+dp[i-2] | 1D |
| 0-1 背包 | dp[i][w] = 前 i 物容量 w 的 max 价值 | dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi]+vi) | 2D |
| LCS | dp[i][j] = 前缀 i 和 j 的 LCS 长度 | 字符相等则 dp[i-1][j-1]+1，否则取 max | 2D |
| 编辑距离 | dp[i][j] = word1 前 i 到 word2 前 j 的代价 | 相等则 dp[i-1][j-1]，否则 1+min(删/插/替) | 2D |
常见陷阱
| 卡点 | 怎么办 |
|---|---|
| 二维转一维改错 | 牢记：0-1 反向，完全正向 |
| 初始化漏了 | dp 数组多加 1，索引对齐语义 |
| 忘记代价加 1 | 先写伪代码确认三种操作代价均为 1 |
通关挑战
python
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1,2,5], 11)) # 3 (5+5+1)旅人笔记
所有序列 DP 本质上都一样——到第 i 步时基于前几步的状态做一次选择。区别只在于聚合函数和边界条件。把 0-1 背包、LCS 和编辑距离吃透，剩下的 DP 变体只是在这三个模型上加加减减。
下一步：贪心算法
DP 每一步考虑所有可能。如果某个问题在每个决策点只需选"当前最优"那个——全局就是最优解呢？