18、递归与动态规划：从递归到DP的转化。以爬楼梯问题为例。
递归和动态规划，说白了就是一对孪生兄弟。很多同学学完递归后，觉得动态规划是另一套新东西，其实不是。我个人习惯把动态规划看作是「加了备忘录的递归」——你想想看，递归之所以慢，是因为它重复计算了太多子问题。动态规划要做的，就是把那些重复计算的结果存起来，下次直接用。
今天我们就以经典的爬楼梯问题为例，一步步从递归走到动态规划。这个过程，我当年在项目中优化一个路径规划算法时也用过，效果立竿见影。
18.1 爬楼梯问题：先看递归解法
问题很简单：你正在爬楼梯，每次可以爬 1 级或 2 级台阶。问爬到第 n 级台阶有多少种不同的方法？
我们先从递归的角度思考。假设 f(n) 表示爬到第 n 级台阶的方法数。那么：
- 爬到第 n 级，最后一步要么是从第 n-1 级跨 1 级上来，要么是从第 n-2 级跨 2 级上来。
- 所以 f(n) = f(n-1) + f(n-2)。
- 边界条件：f(1) = 1，f(2) = 2。
代码写出来非常简洁：
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairs(n - 1) + climbStairs(n - 2);
}嗯，这里要注意。这段代码虽然正确，但效率极低。n=40 的时候，你的电脑可能就要卡几秒钟了。为什么会这样？
核心问题：递归树中存在大量重复计算。比如 f(5) 会计算 f(4) 和 f(3)，而 f(4) 又会计算 f(3) 和 f(2)……f(3) 被重复计算了多次。随着 n 增大，重复量呈指数级增长。
18.2 从递归到记忆化搜索
我曾经在项目中遇到过一个类似的递归爆炸问题。当时处理一个多阶段决策问题，递归深度只有 20，但运行时间已经无法忍受。后来我加了一个数组做缓存，速度提升了上千倍。
这个思路就是记忆化搜索——说白了，就是给递归加个「备忘录」：
int memo[100] = {0};
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (memo[n] != 0) return memo[n]; // 查备忘录
memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
return memo[n];
}你看，只加了三行代码，时间复杂度就从 O(2^n) 降到了 O(n)。这就是动态规划的雏形——「用空间换时间」。
一个小技巧：我习惯把 memo 数组初始化为 -1，而不是 0。因为有些问题的结果可能就是 0，用 0 做「未计算」标记会出 bug。爬楼梯问题结果都是正数，所以用 0 没问题，但养成好习惯总没错。
18.3 真正的动态规划：自底向上
记忆化搜索虽然好，但本质上还是递归。递归有函数调用开销，而且深度太大时可能栈溢出。真正的动态规划，是自底向上迭代计算。
你想想看，我们已知 f(1) 和 f(2)，能不能直接算出 f(3)？然后 f(4)？一直算到 f(n)？当然可以：
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int dp[100] = {0};
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}这就是标准的动态规划解法。我们用一个 dp 数组，从最小的子问题开始，一步步往上推。没有递归调用，没有重复计算，干净利落。
18.4 状态压缩：把空间也省下来
观察上面的代码，你会发现 dp[i] 只依赖 dp[i-1] 和 dp[i-2]。也就是说，我们其实不需要整个数组，只需要两个变量就够了。
我在项目中做嵌入式开发时，内存非常紧张，这种优化就特别实用：
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int prev2 = 1; // f(1)
int prev1 = 2; // f(2)
int curr;
for (int i = 3; i <= n; i++) {
curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return curr;
}空间复杂度从 O(n) 降到了 O(1)。这就是动态规划中的「状态压缩」技巧。
18.5 三种方法的对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 纯递归 | O(2^n) | O(n)（栈空间） | 仅用于理解问题，不实用 |
| 记忆化搜索 | O(n) | O(n) | 递归思路清晰，n 不太大时 |
| 动态规划（自底向上） | O(n) | O(n) 或 O(1) | 生产环境首选 |
避坑指南：我曾经在面试中看到有人一上来就写动态规划，结果边界条件搞错了。我的建议是：先写递归，确认逻辑正确，再改成动态规划。这样既不容易出错，面试官也能看到你的思考过程。
18.6 从爬楼梯到一般规律
爬楼梯问题虽然简单，但它揭示了递归转动态规划的通用套路：
- 定义状态：明确 dp[i] 表示什么。这里 dp[i] 是爬到第 i 级的方法数。
- 找状态转移方程：dp[i] 怎么从更小的状态推出来？这里是 dp[i] = dp[i-1] + dp[i-2]。
- 确定初始条件：最小的子问题是什么？这里是 dp[1] = 1, dp[2] = 2。
- 确定计算顺序：从小往大算，保证计算 dp[i] 时 dp[i-1] 和 dp[i-2] 已经算好了。
你想想看，很多看似复杂的动态规划题，本质上都是这个套路。区别只在于状态定义更复杂、转移方程更绕、初始条件更多。
18.7 本章知识体系
下面这张图总结了从递归到动态规划的完整转化路径：
从图中可以清晰地看到：递归是起点，记忆化搜索是过渡，动态规划是终点。每一步都在解决上一步的痛点。我个人建议初学者先走完这三步，不要一上来就想着写最优解。先把递归写对，再优化，这样思路最清晰。
好了，爬楼梯问题就讲到这里。记住这个套路，下一章我们会用同样的思路去解决更复杂的问题——比如背包问题。到时候你会发现，核心思想其实一模一样。
公众号:蓝海资料掘金营，微信deep3321