主题
界面
递归、分治与动态规划
1. 本节定位
《基础算法：排序与二分查找》讲的是"套循环能解决的问题"；本节讲**"需要把问题拆开"的问题**：
text
递归：函数调用自己 → 结构天然自相似（树、目录、括号）
分治：拆成两半，分别解决再合并 → 归并排序、快速选择
DP： 拆成子问题，缓存结果 → 爬楼梯、背包、最长子序列★ 三者的关系 ✓：分治和 DP 都是递归的"优化版" ✓
- 分治：子问题互不重叠 → 直接拆 ✓
- DP：子问题重叠 → 必须缓存 ✓✓
2. 学习目标
- 能说出朴素递归为什么会指数爆炸，并用实测数字说明 ★★★；
- 掌握"暴力递归 → 记忆化 → 递推"这条优化路径 ★★★；
- 知道分治的适用条件（子问题不重叠） ★★；
- 知道 DP 的两个核心动作（找状态转移 + 压缩空间） ★★★；
- 知道递归的栈深度风险与替代方案 ★★。
3. 前置知识检查
- 会写递归方法吗？（《多态》）✓
- 知道复杂度的含义吗？（《时间复杂度和空间复杂度》）✓
4. 为什么需要这个知识
先看一个"教科书式的性能事故" ✗：
java
static long fib(int n) {
return n <= 1 ? n : fib(n - 1) + fib(n - 2); // 看起来简洁优雅
}★ 实测的调用次数：
text
n=20 → 21891 次调用
n=25 → 242785 次
n=30 → 2692537 次
n=32 → 7049155 次
n=34 → 18454929 次 ← 30 ms★ 从 n=20 到 n=34，调用次数涨了 843 倍 ✗✗（n 只涨了 14）
★ 换成递推之后：
text
○ 暴力递归：352 ms（n=40）
○ 记忆化： 0 ms（结果完全一致 ✓）
○ 递推： 0 ms★ 同一个问题，同一台机器：352 ms → 0 ms ✓✓ ——这不是优化，这是"换了个算法" ✓
5. 核心概念
5.1 递归为什么会指数爆炸 ★★★
原因：重复计算 ✗
text
fib(5) 的调用树：
fib(5)
/ \
fib(4) fib(3) ← fib(3) 算了 2 次
/ \ / \
fib(3) fib(2) fib(2) fib(1) ← fib(2) 算了 3 次
/ \
fib(2) fib(1)★ 调用次数就是 2^n 量级 ✓ ——而这些计算里绝大部分是重复的 ✗
★ 实测的"倍增规律" ✓：
| n 每增加 | 调用次数约 × | 耗时约 × |
|---|---|---|
| +5 | ×10 | ×10 ✓ |
| +10 | ×100 | ×100 ✗ |
★ 所以：算法里有个"指数"，就意味着"永远只能用在小规模上" ✗✗
5.2 优化的三步走 ★★★
第一步：写出暴力递归（先保证"思路对"）✓
java
static long climb(int n) {
return n <= 2 ? n : climb(n - 1) + climb(n - 2);
}第二步：加记忆化（把"重复子问题"只算一次）✓✓
java
static long climb(int n, long[] memo) {
if (n <= 2) { return n; }
if (memo[n] != 0) { return memo[n]; } // ★ 查缓存
return memo[n] = climb(n - 1, memo) + climb(n - 2, memo); // ★ 写缓存
}第三步：改成递推 + 压空间（发现状态只依赖前两项）✓✓
java
static long climb(int n) {
if (n <= 2) { return n; }
long prev = 2, prevPrev = 1;
for (int i = 3; i <= n; i++) {
long cur = prev + prevPrev;
prevPrev = prev;
prev = cur;
}
return prev;
}★ 实测（同一个问题，n=40） ✓：
| 解法 | 耗时 | 复杂度 |
|---|---|---|
| ① 暴力递归 | 352 ms | O(2^n) |
| ② 记忆化 | 0 ms | O(n) |
| ③ 递推（滚动数组） | 0 ms | O(n) 时间 / O(1) 空间 ✓✓ |
★ 三步走的价值 ✓✓：
第一步保证正确性，第二步消灭重复计算，第三步消灭多余空间 ✓
面试时可以按这个顺序说，工程里可以按这个顺序写 ✓（先写对，再优化 ✓）
5.3 分治：子问题不重叠 ★★
分治的三个步骤：
text
① 分解：把问题拆成同构的子问题
② 解决：递归处理子问题
③ 合并：把子问题的结果组合起来★ 分治的关键前提：子问题之间不重叠 ✓✓
| 算法 | 分解方式 | 合并 |
|---|---|---|
| 归并排序 ★★ | 拆成两半 | 合并两个有序数组（O(n)）✓ |
| 快速排序 ★★ | 按基准分区 | 无需合并（原地）✓ |
| 快速选择 ★★★ | 只递归一边 | 无需合并 ✓✓ |
★ 实测数据 ✓：
text
归并排序 100 万个元素：215 ms（O(n log n)）
快速选择第 100 小的元素： 16 ms（O(n)）★ 快速选择为什么能 O(n) ✓✓：
它只递归"含目标的那一边"，丢掉另一边 ✓
所以工作量是 n + n/2 + n/4 + ... = 2n = O(n) ✓✓
这就是分治的精髓："能丢掉一半，就不要处理两半" ✓
★ 与二分查找的关系 ✓：二分查找也是"只走一边" ✓ ——所以它也是 O(log n) ✓
5.4 动态规划的两个核心动作 ★★★
动作一：找状态转移方程 ✓
问自己三个问题：
| 问题 | 例子（0-1 背包） |
|---|---|
| 状态是什么？ ★★ | dp[i][w] = 前 i 个物品、容量 w 时的最大价值 |
| 选择是什么？ ★★ | 第 i 个物品"拿"还是"不拿" |
| 怎么转移？ ★★ | dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi) ✓ |
动作二：压缩空间 ✓✓
实测数据：
text
二维 DP（501 × 3001）：15 ms（结果 13085）
一维滚动数组 ： 8 ms（结果 13085）
空间从 1503501 降到 3001（省 99.8%），时间相近★ 压缩的关键细节（这条最容易写错） ✓✓：
java
// ✓ 一维数组必须"倒着遍历"
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}为什么倒着走 ✓：
| 方向 | 效果 |
|---|---|
| 倒着走 ✓✓ | dp[w - weight] 还是"上一轮"的值 → 每个物品只用一次 ✓ |
| 正着走 ✗✗ | dp[w - weight] 已被本轮更新 → 变成"完全背包"（物品可重复取） ✗ |
★ 这个细节是"背包问题"最经典的坑 ✓✓ ——写错了程序不报错，只是答案不一样 ✗
★ 一条实用的自检 ✓：如果答案比预期大，先检查"是不是正着遍历了" ✓✓
5.5 递归的栈深度风险 ★★
实测（《树、堆与哈希表》 的树遍历）：
text
树深度 10000（退化成链表）：递归遍历成功（临界）★ 三条判断 ✓：
| 深度 | 建议 |
|---|---|
| O(log n)（平衡树、二分）✓ | 放心用递归 ✓ |
| 深度 = n 但 n 可控（如 n < 1 万）⚠️ | 可用，但要意识到临界 |
| 深度可能很大（链表、目录树、用户输入）✗✗ | 用显式栈 / 迭代 ✓✓ |
★ 一个更关键的区分 ✓✓：
"递归深度"与"问题规模"不是一回事 ✓
归并排序的规模是 n，深度是 log n ✓✓（因为它每次砍一半）
而"链表的递归遍历"规模是 n，深度也是 n ✗✗
★ 所以判断标准是："递归深度会不会随数据增长" ✓
★ 顺带一个 DP 的替代 ✓：
text
递归 + 记忆化 ⟺ 自顶向下 DP
递推（for 循环）⟺ 自底向上 DP ← ★ 天然没有栈溢出风险 ✓如果状态转移的顺序是确定的（如背包按物品、爬楼梯按 n），优先写递推 ✓✓
6. 递进示例
6.1 最小示例：递归的三要素
java
static int factorial(int n) {
if (n <= 1) { return 1; } // ① 终止条件（必须有，且要能到达）
return n * factorial(n - 1); // ② 递归调用（规模要缩小）
} // ③ 结果利用（把子结果组合起来）6.2 业务示例：爬楼梯的三种写法
见 5.2 ✓
6.3 反例：不缓存的递归
java
static long climb(int n) { return n <= 2 ? n : climb(n - 1) + climb(n - 2); }
// n=40 就要 352 ms，n=50 要几十分钟 ✗✗7. 完整可运行代码与实测
代码：labs/cs-basics/src/main/java/cn/kb/learn/cs/RecursionLesson.java
运行：
powershell
cd labs
.\mvnw.cmd -pl cs-basics compile
java "-Dstdout.encoding=UTF-8" -cp cs-basics/target/classes cn.kb.learn.cs.RecursionLesson实测输出（节选）：
text
===== 1. 朴素递归的指数爆炸 =====
n 朴素递归 ms 调用次数
20 0 21891 （结果 6765）
25 1 242785 （结果 75025）
30 4 2692537 （结果 832040）
32 11 7049155 （结果 2178309）
34 30 18454929 （结果 5702887）
===== 2. 同一个问题（爬楼梯）的三种解法 =====
① 暴力递归 O(2^n) ：352 ms
② 记忆化搜索 O(n) ： 0 ms
③ 递推（滚动数组）O(n)/O(1)： 0 ms
三者结果一致：165580141 / 165580141 / 165580141 ✓
===== 4. 0-1 背包：空间压缩的实测 =====
二维 DP（501 × 3001）：15 ms（结果 13085）
一维滚动数组 ： 8 ms（结果 13085）
→ 空间从 1503501 降到 3001（省 99.8%），时间相近 ✓★ 三条可落地的结论 ✓：
| # | 结论 | 依据 |
|---|---|---|
| ① | 看到递归里有"重复调用同一个参数"就加缓存 | 352 ms → 0 ms ✓ |
| ② | 背包等 DP 的一维实现必须倒着遍历 | 正着走会变成"可重复取" ✗ |
| ③ | 能写递推就别写递归 | 无栈溢出风险，通常也更快 ✓ |
8. Debug 观察点
- 把
fib的 n 从 34 加到 40：观察耗时从 30 ms 涨到几百毫秒（倍增规律）★； - 把记忆化数组去掉
if (memo[n] != 0)那行：观察耗时回到暴力水平 ✓； - 把背包的一维遍历改成正序：观察结果变大 ✗✗（变成完全背包）★；
- 打印递归的深度（加一个 depth 参数）：观察快速选择与归并的深度差异 ★；
- 把归并排序改成"递归拆分 + 不合并"：观察结果错误 ✓。
9. 常见错误
| # | 错误 | 说明 |
|---|---|---|
| 1 | 递归没有终止条件或无法到达 ✗✗ | 栈溢出 ✓ |
| 2 | 重复子问题不加缓存 ✗✗ | 指数爆炸（5.1）✗ |
| 3 | 背包一维数组正序遍历 ✗✗ | 变成完全背包，答案偏大 ✓ |
| 4 | 对"深度随数据增长"的结构用递归 ✗ | 栈溢出（5.5）✓ |
| 5 | 记忆化的"未计算"标记与合法值冲突 ⚠️ | 如用 0 当标记，但 0 是合法答案 ✗ → 用 -1 或 null ✓ |
| 6 | 分治时两边都递归，但只有一边有用 ✗ | 快速选择就是"只走一边"的例子 ✓ |
| 7 | 递归返回值忘记使用（写成 f(n-1); f(n-2);）✗✗ | 结果永远是 0 ✓ |
10. 动手实验
目标：亲手体验"指数爆炸"与"三步优化"。
步骤：
- 跑
RecursionLesson，记录各 n 的调用次数 ✓； - 自己写一个"斐波那契 + 计数"，n 从 20 加到 35，画出调用次数曲线 ★；
- 加上
memo数组，再画一次 → 观察它变成直线 ✓✓； - 把它改成 int 溢出（n=47 时超出
int）→ 观察结果变负 ✗（《计算机组成与二进制》 的溢出）★； - 把背包的一维版正序跑一遍，对比结果 ✓。
验收方式：能说出"n 加倍时，朴素的斐波那契大约慢多少倍"。
扩展任务：用 DP 解决**"最长递增子序列（LIS）"**：
- 先写 O(n²) 的 DP（
dp[i]= 以 i 结尾的最长长度）✓； - 再想 O(n log n) 的做法（提示：维护一个"最小结尾数组"，用二分更新）★★；
- 对比两者在 n=10000 上的耗时 ✓
11. 练习题
- 判断：递归都可以改写成循环。（对 / 错）
- 填空：DP 优化的两步是 ______ 与 ______；一维背包必须 ______ 遍历。
- 简答：为什么快速选择是 O(n)，而快速排序是 O(n log n)？
- （代码阅读）
java
static int ways(int n, int[] memo) {
if (n == 0) { return 1; }
if (n < 0) { return 0; }
if (memo[n] != 0) { return memo[n]; }
return memo[n] = ways(n - 1, memo) + ways(n - 2, memo);
}这个记忆化有什么问题？（提示：memo[n] != 0 作为"已计算"的判据）★ 5. （编程）用 DP 解决"最小硬币数"：给定硬币面额数组，求凑出金额 amount 的最少硬币数，凑不出返回 -1。
参考答案（要点）
- 对。任何递归都能用"显式栈 + 循环"改写 ✓ ——但可读性可能下降 ✓
- 加记忆化（消灭重复计算）；压缩空间（滚动数组）；倒序 ✓
- 因为快速选择每次只递归含目标的一边（工作量 n + n/2 + n/4 + … = 2n）✓★
- 问题在于"0 是合法答案" ✗ ——如果某个
ways(n)的结果真的是 0，它每次都会被重算 ✓ 改法：用-1作"未计算"标记，或用一个boolean[] visited✓ - 要点：
dp[i] = min(dp[i - coin] + 1)，初始化为一个大值（表示不可达） ✓ 注意：dp[0] = 0，且要处理"无法凑出"（保持大值则返回 -1）✓
12. 掌握标准
- [ ] 能说出朴素递归为什么指数爆炸，并给出实测数字 ★★★；
- [ ] 掌握"暴力 → 记忆化 → 递推"三步走 ★★★；
- [ ] 知道分治的前提是子问题不重叠，且"能丢一半就丢一半" ★★★；
- [ ] 知道 DP 的两个动作：状态转移 + 空间压缩 ★★★；
- [ ] 知道一维背包必须倒序遍历，并知道正序的后果 ★★★；
- [ ] 会判断"递归深度是否会随数据增长" ★★；
- [ ] 知道"记忆化标记不能与合法值冲突" ✓。
13. 扩展资源
14. 下一步学习
《LeetCode 刷题方法与 Java 解题模板》：把这些思路变成可复用的模板。
后续知识
暂无
进度只保存在本机浏览器，可随时清除