适用读者：看得懂 DP 题解，但自己写不出转移方程的人。
前置：S03-B01。
实测环境：Python 3.12.3（爬楼梯三版对比）；实测日期 2026-11-05。
覆盖旧文：10、44、53、62、63、64、70、72、87、91、97（11 张卡，1,354 点）。
覆盖扩展：E-S03-019（状态压缩与滚动数组）。
补写：#53、#62、#91、#97（空壳卡，E-S03-119~E-S03-122）。
上一篇：S03-J04 · 回溯与搜索：把"枚举"写成树
下一篇：S03-J06 · 栈与单调栈。
1. 一句话结论
DP 不是"想出来"的，是"从暴力递归改出来"的：写出递归 → 发现重复子问题 → 加记忆化 → 改成自底向上。
| 步骤 | 动作 | 产出 |
|---|---|---|
| ① | 写暴力递归 | f(n) = f(n-1) + f(n-2) |
| ② | 找重复子问题 | n=35 时 f(30) 被算了几十万次（实测耗时差 4.7 万倍） |
| ③ | 记忆化（自顶向下） | 加缓存，O(n) |
| ④ | 自底向上（迭代） | 去递归，O(n) 时间 + O(1) 空间 |
四步里最难的是第 ① 步：状态定义对了，转移方程几乎是自然写出来的。
2. 实测：重复子问题有多贵
爬楼梯（f(n) = f(n-1) + f(n-2)，n=35）：
| 实现 | 耗时 | 相对 |
|---|---|---|
| 纯递归（无缓存） | 2,488.7 ms | 基准 |
| 记忆化递归 | 0.052 ms | 47,860× 快 |
| 迭代（滚动两变量） | 0.011 ms | 226,000× 快 |
结果都是 14930352。
这条数据说明 DP 的本质：不是"算法更聪明"，是"把重复计算删掉"。n=35 时递归树有约 3,000 万次调用，其中绝大多数是重复的。
3. 状态定义：四问法
拿到题，按顺序问四个问题：
| 问 | 例子（#62 不同路径） |
|---|---|
| ① 状态是什么？ | dp[i][j] = 走到 (i,j) 的路径数 |
| ② 转移从哪来？ | 只能从上方或左侧来：dp[i][j] = dp[i-1][j] + dp[i][j-1] |
| ③ 边界是什么？ | 第一行/第一列都是 1（只有一条路） |
| ④ 遍历顺序？ | 从上到下、从左到右（依赖已算过） |
判据："状态"必须包含"做出决策所需的全部信息"。少一个维度 → 无法转移；多一个维度 → 复杂度爆炸。
4. 代表题精讲
4.1 #53 最大子数组和（补写 E-S03-119）
状态：cur = 以 i 结尾的最大和。
转移：cur = max(a[i], cur + a[i])——"续上"还是"重开"二选一。
int maxSubArray(int[] a) {
int cur = a[0], best = a[0];
for (int i = 1; i < a.length; i++) {
cur = Math.max(a[i], cur + a[i]);
best = Math.max(best, cur);
}
return best;
}
| 复杂度 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1)（滚动） |
为什么不能只维护 best：cur 表示"必须以 i 结尾"，这是转移成立的前提。
4.2 #62 不同路径（补写 E-S03-120）
int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1); // 第一行全 1
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[j] += dp[j-1]; // dp[j]（上）+ dp[j-1]（左）
return dp[n-1];
}
滚动数组：二维压成一维，dp[j] 在更新前是"上一行"，更新后是"本行"。
#63 带障碍：障碍处 dp[j] = 0，且初始化第一行遇到障碍后全 0。
4.3 #91 解码方法（补写 E-S03-121）
状态：dp[i] = 前 i 个字符的解码数。
转移：
- 当前字符
1–9→dp[i] += dp[i-1] - 前两位
10–26→dp[i] += dp[i-2]
int numDecodings(String s) {
int n = s.length(), prev2 = 1, prev1 = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; i++) {
int cur = 0;
int one = s.charAt(i-1) - '0';
int two = (s.charAt(i-2)-'0') * 10 + one;
if (one >= 1 && one <= 9) cur += prev1;
if (two >= 10 && two <= 26) cur += prev2;
prev2 = prev1; prev1 = cur;
}
return prev1;
}
坑："01" 这种前导 0 不合法（只能整体两位解 10–26）；"0" 单独出现返回 0。
4.4 #97 交错字符串（补写 E-S03-122）
状态：dp[i][j] = s1[0..i) 与 s2[0..j) 能否拼成 s3[0..i+j)。
转移：看 s3 的最后一个字符来自 s1 还是 s2：
dp[i][j] = (i>0 && s1.charAt(i-1)==s3.charAt(i+j-1) && dp[i-1][j])
|| (j>0 && s2.charAt(j-1)==s3.charAt(i+j-1) && dp[i][j-1]);
前置检查：m + n != s3.length() 直接 false。
4.5 #72 编辑距离：二维 DP 的代表
dp[i][j] = min(
dp[i-1][j] + 1, // 删除
dp[i][j-1] + 1, // 插入
dp[i-1][j-1] + (a[i-1]==b[j-1] ? 0 : 1) // 替换
)
初始化：dp[i][0] = i、dp[0][j] = j。
4.6 #87 扰乱字符串：区间 DP
dp[i][j][len]：s1 从 i 起、s2 从 j 起、长度 len 是否互为扰乱。枚举分割点 k，两种拼接方式（不交换/交换）任一成立即可。O(n³) 时间 / O(n³) 空间（可优化到 O(n²)）。
5. 11 题模式对照
| 题 | 状态 | 转移要点 |
|---|---|---|
| 10 | dp[i][j] |
* 分"0 次/多次" |
| 44 | dp[i][j] |
* 匹配任意串 |
| 53 | cur |
续上 vs 重开（补写） |
| 62 | dp[j] |
上 + 左（补写） |
| 63 | dp[j] |
障碍置 0 |
| 64 | dp[j] |
min(上, 左) + 值 |
| 70 | 两变量 | 斐波那契 |
| 72 | dp[i][j] |
三操作取 min |
| 87 | dp[i][j][len] |
区间 + 两种拼接 |
| 91 | prev1/prev2 |
一位或两位（补写） |
| 97 | dp[i][j] |
最后一个字符来自哪（补写） |
6. 五个误区
| 误区 | 真相 |
|---|---|
| "DP 靠灵感" | 从暴力递归改；四问法能覆盖大多数题 |
| "记忆化就够，不用迭代" | 迭代常数更小、无栈风险（实测 5× 差距） |
| "状态越多越安全" | 维度爆炸；多余维度会 MLE/TLE |
| "滚动数组总是对的" | 依赖"只用上一行"；若依赖上一行左侧值，要注意覆盖顺序 |
| "空间优化一定更好" | 可读性下降；先写二维，确认正确再压 |
7. 自检
- 爬楼梯 n=35，纯递归/记忆化/迭代的实测耗时各是多少？
- 四问法的四个问题分别是什么？
- #53 为什么不能用"前缀和 + 全局最大"直接做？
- #62 滚动数组里
dp[j] += dp[j-1]为什么是"上 + 左"？ - #91 的
"01"与"10"分别返回什么？为什么？
8. 下一篇
S03-J06 · 栈与单调栈：把"最近更大/更小"变成 O(n)
DP 处理"最值/方案数"，最后一篇处理"最近邻"：单调栈把 O(n²) 的"向左找第一个更大"压成 O(n)（实测 10 万数据：单调栈 68.6 ms，暴力外推约 3 秒）。
本篇属于系列《S03 · 数据结构与算法》。旧文来源：11 张题解卡；补写 #53/#62/#91/#97（E-S03-119~122）。爬楼梯三版实测（2,488.7 / 0.052 / 0.011 ms）为 2026-11-05。