元数据卡
- 前置知识：递归（Vol 1）、分治
- 预计时间：20 分钟
- 核心难度：进阶
- 完成标志：能识别重叠子问题和最优子结构，能用记忆化搜索解决斐波那契级问题
你的进度
你已经在递归森林里走了很久。但有一件事让你不爽：斐波那契递归 n=40 就卡得要死，n=100 直接爆炸。回调栈里相同参数重复算了上千遍。老陈的信里说："有些答案，记住它就好。"这就是动态规划的起点。
你的任务 学会三个核心概念：重叠子问题、最优子结构、记忆化 vs 表格化。看完就能动手解决所有和斐波那契一模一样的 DP 入门问题。
石碑上的斐波那契谜题
你发现一块石碑，上面刻着古老的谜题。前人的笔记写着：
python
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
# n=50 等很久，指数爆炸你翻开笔记，发现老陈的批注——"你每次走了同一条路两次？做标记，走过了就记住。"
python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1: return n
return fib_memo(n-1) + fib_memo(n-2)
# n=100 瞬出 354224848179261915075重叠子问题
朴素递归 fib(30) 被重复算了 8328040 次。加缓存后每个 n 只算 1 次。
判断标准： 画递归树找相同子树多次出现。有 -> DP 候选；没有 -> 分治。
最优子结构
大问题的最优解，包含子问题的最优解。从东岸到西岸的最短路径经过山腰水源，那么东岸到水源那段一定也是最短路。否则可以换更短的，整体就更短。
陷阱： 无权图的最长简单路径——最长路径的子路径不一定是子问题的最长路径。
状态转移方程
告诉我前一步的状态，我就能推出当前步。斐波那契的状态转移：dp[n] = dp[n-1] + dp[n-2]。
python
def fib(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# fib(50) = 12586269025java
// Java: 自底向上
public class FibDP {
public static int fib(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 void main(String[] args) {
System.out.println(fib(50));
}
}
// 编译: javac FibDP.java 运行: java FibDP
// 预期输出: 12586269025记忆化 vs 表格法
| 维度 | 记忆化递归（Top-down） | 表格迭代（Bottom-up） |
|---|---|---|
| 方向 | 自顶向下 | 自底向上 |
| 实现 | 递归 + 缓存 | 循环 + 数组 |
| 优点 | 只算需要的状态 | 无递归栈溢出 |
| 缺点 | 递归深度限制 | 可能算不需要的状态 |
python
# Top-down
def fib_top_down(n, memo=None):
if memo is None: memo = {}
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_top_down(n - 1, memo) + fib_top_down(n - 2, memo)
return memo[n]
# Bottom-up 空间优化到两个变量
def fib_bottom_up(n):
if n <= 1: return n
prev2, prev1 = 0, 1
for i in range(2, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
# fib_bottom_up(100) = 354224848179261915075实战： 面试先用记忆化快速写原型，再说"优化为 Bottom-up 省掉递归开销"。实际谁敢用递归算大 n？老老实实迭代。
爬楼梯——斐波那契换皮
打完斐波那契，你会发现很多 DP 问题都是它披着不同外衣。爬楼梯就是第一个：到第 i 阶 = 从 i-1 阶跨一步 + 从 i-2 阶跨两步。
python
def climb_stairs(n):
if n <= 2: return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# climb_stairs(10) = 89常见陷阱
| 卡点 | 症状 | 怎么办 |
|---|---|---|
| 状态定义不清楚 | 不知道 dp[i][j] 代表啥 | 先写人话："dp[i] = 前 i 个物品..." |
| 边界搞错 | 索引越界 | 加 dummy 行/列 |
| 转移顺序反了 | 结果永远是 0 | 画 DP 表标出依赖关系 |
通关挑战
python
def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
print(rob([2, 7, 9, 3, 1]))
# 预期: 12 (偷 2+9+1)旅人笔记
DP 不是一种算法，是一种思维转换——从"怎么算"到"怎么记住"。两个技巧：先写暴力递归再找重复参数；把数组多加 1 个用 dummy 行处理边界。
下一步：经典 DP 问题
斐波那契是 DP 的"Hello World"。接下来面对背包、LCS、编辑距离这些真正的问题。