动态规划：为什么记忆化比递归快几千倍？

一句话结论（30s）

动态规划比暴力递归快几千倍，是因为它把「重叠子问题」的重复计算用数组缓存起来，把指数级 O(2^n) 的递归换成 O(n) 的单次计算——本质是用空间换时间，两个识别条件是「最优子结构」和「重叠子问题」。

核心原理（2min）

重叠子问题：fib(50) 会反复计算 fib(30) 数千次，导致指数爆炸 O(2^n)。
记忆化搜索（自顶向下）：加 memo 缓存，每个 n 只算一次，递归结构不变，O(2^n) → O(n)。
自底向上 DP：从最小子问题依次递推到 n，状态转移方程 dp[i] = dp[i-1] + dp[i-2]。
空间优化：只保留最近两个状态，O(n) → O(1)。

💭 思考：看到什么信号该想到动态规划？—— 先问两个问题：① 大问题的答案能不能由小问题拼出来？（最优子结构）② 这些小问题会不会被反复问到？（重叠子问题）。以 fib 为例，fib(n) 由 fib(n-1)+fib(n-2) 拼出来，且 fib(n-2) 会被算两遍、fib(30) 会被算几千遍——两个条件同时命中，说明「重复计算」才是瓶颈，用表缓存就能把指数换成线性。所以别急着写代码，先找「能不能拆 + 会不会重复」。

底层深入（5-10min）

斐波那契的递归陷阱

int fib(int n) {
    if (n <= 2) return 1;
    return fib(n-1) + fib(n-2);  // ← fib(38) + fib(37) 各自递归，指数爆炸
}

fib(50) 需要计算 fib(30) 数千次——同一个子问题被反复计算（重叠子问题）。为什么递归会慢到”算不出来”？ 因为每次调用都分裂成两个子调用，没有复用，计算量随 n 呈 2 的幂增长；问题不在于”递归思想”，而在于”同一件事被重复做了几千遍”。

方法一：记忆化搜索（自顶向下）

int[] memo = new int[n + 1];
int fib(int n) {
    if (n <= 2) return 1;
    if (memo[n] != 0) return memo[n];  // 算过的不重复
    return memo[n] = fib(n-1) + fib(n-2);
}

每个 n 只计算一次。递归结构不变，加了一个缓存数组。时间复杂度从 O(2^n) → O(n)。

💭 思考：为什么只是加一个 memo 数组，复杂度就从指数掉到线性？—— 递归慢不是因为「递归」这个写法，而是因为同一子问题被重复计算。想清楚这点，最省事的改法就是：进函数先查「算过没有」，算过就直接返回。这样「重复调用」被拦在入口，每个 n 真正只展开一次，递归树从满二叉树退化成一条链——结构没变，重复计算没了。记忆化其实是「自顶向下」版的 DP：先写最自然的递归，再补缓存。

方法二：自底向上 DP

int fib(int n) {
    if (n <= 2) return 1;
    int[] dp = new int[n + 1];
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];  // 状态转移方程
    return dp[n];
}

递归的”最后结果”变成了循环的”第一结果”。DP 表从最小的子问题开始依次推算到大问题。为什么自底向上通常更快、更省？ 因为它按顺序把每个子问题只算一遍、算完就存进数组，既消除了递归调用的栈开销，又天然满足”先算小的再算大的”依赖顺序。

💭 思考：状态转移方程 dp[i]=dp[i-1]+dp[i-2] 是怎么「想」出来的？—— 不要背方程，回到定义：先定 dp[i] 表示「第 i 个斐波那契数」，那它和前面是什么关系？由斐波那契的定义本身就是 f(n)=f(n-1)+f(n-2)，把下标换成 dp 就是转移方程。所以推导顺序永远是：先定「状态代表什么」，再问「这个状态由哪些更小的状态决定」，方程自然就出来了。这也是 DP 题最容易卡的地方——状态定义错了，后面全错。

方法三：空间优化 DP

int fib(int n) {
    if (n <= 2) return 1;
    int prev2 = 1, prev1 = 1, cur = 0;
    for (int i = 3; i <= n; i++) {
        cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return cur;  // 空间从 O(n) → O(1)
}

识别 DP 的两个条件：① 最优子结构（大问题的最优解包含子问题的最优解）② 重叠子问题（相同子问题被反复调用）。DP 的本质是用空间换时间——把 O(2^n) 的重复计算换成 O(n) 的单次计算 + O(n) 的数组存储。

💭 思考：为什么空间还能从 O(n) 再压到 O(1)？—— 观察转移方程 dp[i]=dp[i-1]+dp[i-2]：算 dp[i] 时只用得到前两项，更早的 dp[i-3] 及之前再也不会被回看。既然「用过的就不再需要」，就不必为整张表买单，只要滚动保留最近的 2 个状态即可。这个「看依赖范围，砍掉不用的列」的思路在很多 DP 题里都能复用：转移只依赖前一项/前两项，空间就能从 O(n) 降到 O(1)。

章末提问

怎么判断一道题该用动态规划而不是普通递归？ 结论：看它是否同时满足”最优子结构 + 重叠子问题”，即大问题的最优解由子问题最优解组成、且同一子问题会被反复计算；满足就用 DP 缓存避免指数爆炸。
记忆化搜索（自顶向下）和自底向上 DP 有什么本质区别？ 结论：本质都是”每个子问题只算一次”，只是记忆化保留递归结构、按需计算，自底向上用循环按依赖顺序推；后者省去递归栈开销、更容易做空间优化。
为什么说 DP 是”用空间换时间”？ 结论：因为它用一张表（数组）存下已算过的子问题结果，把 O(2^n) 的重复计算换成 O(n) 的单次计算 + O(n) 存储；多花的空间买回了指数级的时间。

动态规划——最优子结构与状态转移方程