空间最优解全链路剖析)
在C语言算法笔试和校招面试中，爬楼梯问题是动态规划入门的「敲门砖」，也是区分新手和进阶选手的经典分水岭。很多同学第一反应会写递归解法，结果直接超时、栈溢出；今天从暴力递归→记忆化搜索→动态规划→空间压缩，全链路拆解这道经典难题，彻底讲透动态规划的核心思维。
一、经典笔试原题
假设你正在爬楼梯，需要爬 n 阶才能到达楼顶。
每次你只能爬 1阶 或 2阶 台阶，求有多少种不同的爬楼方法可以到达楼顶。
- 输入 n=2 ，输出 2 （1+1、2）
- 输入 n=3 ，输出 3 （1+1+1、1+2、2+1）
- 限制： 1 ≤ n ≤ 45
二、核心难点拆解
难点1：暴力递归的致命陷阱
新手最容易写出纯递归解法：
// 错误暴力递归，n稍大就超时、栈溢出
int climbStairs(int n) {
if(n <= 2) return n;
return climbStairs(n-1) + climbStairs(n-2);
}
- 问题：存在大量重复计算，比如 f(5) 会重复计算 f(3) 、 f(2) 无数次
- 时间复杂度：O(2ⁿ)，指数级爆炸，n=45时完全无法运行
- 还会导致递归栈溢出，直接程序崩溃
难点2：动态规划的状态转移核心
最优解法的底层逻辑，是找到递推关系：
- 定义 dp[i] ：到达第 i 阶楼梯的总方法数
- 到达第 i 阶只有两种路径：1. 从 i-1 阶爬1阶上来 → 方法数 = dp[i-1]
2. 从 i-2 阶爬2阶上来 → 方法数 = dp[i-2]
- 状态转移方程： dp[i] = dp[i-1] + dp[i-2] （本质是斐波那契数列）
- 边界条件： dp[1]=1 ， dp[2]=2
难点3：空间压缩优化思维
普通动态规划需要开 dp[] 数组，空间复杂度O(n)；
进阶优化：只保留前两个状态，滚动更新
- 用变量 a 存 dp[i-2] ， b 存 dp[i-1]
- 每次迭代计算 c = a+b ，再滚动赋值，空间复杂度直接降到O(1)，达到面试满分最优解
三、C语言完整可运行最优代码
#include <stdio.h>
// O(1)空间、O(n)时间 最优动态规划解法
int climbStairs(int n) {
// 边界特判
if (n <= 2) {
return n;
}
// a: dp[i-2], b: dp[i-1]
int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int c = a + b; // 计算当前阶方法数
a = b; // 滚动更新：前前阶→前阶
b = c; // 滚动更新：前阶→当前阶
}
return b;
}
int main() {
printf("n=2 方法数：%d\n", climbStairs(2)); // 输出2
printf("n=3 方法数：%d\n", climbStairs(3)); // 输出3
printf("n=10 方法数：%d\n", climbStairs(10));// 输出89
return 0;
}
四、易错难点深度剖析
1. 绝对不要写纯递归
指数级时间复杂度，n>30就严重超时，面试直接0分，必须杜绝。
2. 边界条件不能写错
n=1 返回1、 n=2 返回2，很多同学会误写成斐波那契初始值（0、1），导致结果错位。
3. 滚动赋值顺序不能颠倒
必须先算 c = a+b ，再更新 a = b 、 b = c ，顺序错了会覆盖旧值，逻辑完全崩盘。
4. 递推模型的通用性
这套「状态定义→转移方程→空间压缩」的模板，是所有动态规划题的通用解题思路，后续打家劫舍、不同路径、零钱兑换等难题，全部可以套用。
五、算法学习总结
爬楼梯问题是动态规划入门的黄金例题，完整展现了算法优化的全链路：
从指数级暴力递归 → 线性时间动态规划 → 常数空间最优解，核心思维从「重复递归」升级为「状态复用」。
吃透这道题，就能彻底打通动态规划的底层逻辑，后续所有线性递推类算法难题，都能快速上手拆解，是笔试面试必掌握的核心基础。
