LeetCode Hot 100 - 爬楼梯完全题解
题目描述
假设你正在爬楼梯。需要n阶你才能到达楼顶。
每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
text
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
text
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
示例 3：
text
输入：n = 4 输出：5 解释：5种方法： 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2
示例 4：
text
输入：n = 1 输出：1
约束条件：
1 <= n <= 45
解题思路
核心思想：这是一个经典的动态规划问题，本质上就是斐波那契数列。
状态转移方程：
text
dp[i] = dp[i-1] + dp[i-2]
解释：爬到第i阶楼梯的方法数 = 爬到第i-1阶的方法数（再爬 1 阶）+ 爬到第i-2阶的方法数（再爬 2 阶）
边界条件：
text
dp[1] = 1 // 只有 1 种方法：1 阶 dp[2] = 2 // 2 种方法：1+1 或 2
方法一：递归（暴力解法）
思路
直接按照状态转移方程递归求解。
代码实现
java
public int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; return climbStairs(n - 1) + climbStairs(n - 2); }复杂度分析
时间复杂度：O(2ⁿ) — 指数级，会超时
空间复杂度：O(n) — 递归栈深度
优缺点
✅ 思路最直观
❌ 效率极低，n=45 时无法运行
方法二：递归 + 记忆化搜索（带备忘录）
思路
使用数组存储已计算过的结果，避免重复计算。
代码实现
java
public int climbStairs(int n) { int[] memo = new int[n + 1]; return dfs(n, memo); } private int dfs(int n, int[] memo) { if (n == 1) return 1; if (n == 2) return 2; if (memo[n] != 0) return memo[n]; memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo); return memo[n]; }复杂度分析
时间复杂度：O(n) — 每个 n 只计算一次
空间复杂度：O(n) — 递归栈 + 备忘录数组
优缺点
✅ 时间复杂度优化到 O(n)
❌ 仍有递归栈开销
方法三：动态规划（DP数组）
思路
使用 DP 数组自底向上计算。
代码实现
java
public int climbStairs(int n) { if (n == 1) return 1; int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }手动模拟
以n = 5为例：
| i | dp[i] | 计算过程 |
|---|---|---|
| 1 | 1 | 边界条件 |
| 2 | 2 | 边界条件 |
| 3 | 3 | dp[2] + dp[1] = 2 + 1 = 3 |
| 4 | 5 | dp[3] + dp[2] = 3 + 2 = 5 |
| 5 | 8 | dp[4] + dp[3] = 5 + 3 = 8 |
结果：8✅
复杂度分析
时间复杂度：O(n) — 一次循环
空间复杂度：O(n) — DP 数组
优缺点
✅ 时间复杂度 O(n)
✅ 思路清晰易懂
❌ 空间复杂度 O(n)，可以优化
方法四：动态规划 + 滚动数组（空间优化）⭐
思路
因为dp[i]只依赖前两个状态，所以只需要两个变量。
代码实现
java
public int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; int prev2 = 1; // dp[i-2] int prev1 = 2; // dp[i-1] int current = 0; for (int i = 3; i <= n; i++) { current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; // 或 current }变量变化过程
以n = 5为例：
| i | prev2 | prev1 | current | 说明 |
|---|---|---|---|---|
| 初始 | 1 | 2 | - | dp[1]=1, dp[2]=2 |
| 3 | 1 | 2 | 3 | current = 2+1=3，然后滚动 |
| 4 | 2 | 3 | 5 | current = 3+2=5 |
| 5 | 3 | 5 | 8 | current = 5+3=8 |
返回 prev1 = 5?等等，这里要注意循环结束后的值！
实际上循环结束后prev1就是dp[n]：
i=3: prev2=1, prev1=2, current=3 → 更新: prev2=2, prev1=3
i=4: prev2=2, prev1=3, current=5 → 更新: prev2=3, prev1=5
i=5: prev2=3, prev1=5, current=8 → 更新: prev2=5, prev1=8
循环结束，返回 prev1=8 ✅
复杂度分析
时间复杂度：O(n) — 一次循环
空间复杂度：O(1) — 只使用三个变量
优缺点
✅ 时间复杂度 O(n)
✅ 空间复杂度 O(1)
✅ 代码简洁
⭐ 面试推荐写法
方法五：通项公式（数学法）
思路
爬楼梯问题本质是斐波那契数列，有闭合解。
斐波那契通项公式：
text
F(n) = (φⁿ - ψⁿ) / √5 其中 φ = (1 + √5) / 2 ≈ 1.618, ψ = (1 - √5) / 2 ≈ -0.618
但注意：爬楼梯数列是F(1)=1, F(2)=2, F(3)=3, F(4)=5...
实际上是斐波那契数列偏移：climbStairs(n) = Fib(n+1)
代码实现
java
public int climbStairs(int n) { double sqrt5 = Math.sqrt(5); double phi = (1 + sqrt5) / 2; double psi = (1 - sqrt5) / 2; // 爬楼梯(n) = Fib(n+1) = (φ^(n+1) - ψ^(n+1)) / √5 double result = (Math.pow(phi, n + 1) - Math.pow(psi, n + 1)) / sqrt5; return (int) Math.round(result); }复杂度分析
时间复杂度：O(log n) —
Math.pow的时间复杂度空间复杂度：O(1)
优缺点
✅ 时间复杂度最优 O(log n)
✅ 空间复杂度 O(1)
❌ 浮点数精度问题（n 较大时可能出错）
❌ 不推荐面试使用（过于数学化）
方法六：矩阵快速幂
思路
利用矩阵乘法快速计算斐波那契数列。
矩阵公式：
text
[ F(n) F(n-1) ] = [ 1 1 ] ^ (n-2) * [ F(2) F(1) ] [ F(n-1) F(n-2) ] [ 1 0 ] [ F(1) F(0) ]
代码实现
java
public int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; int[][] base = {{1, 1}, {1, 0}}; int[][] result = matrixPower(base, n - 2); // result[0][0] * 2 + result[0][1] * 1 return result[0][0] * 2 + result[0][1] * 1; } private int[][] matrixPower(int[][] matrix, int n) { int[][] result = {{1, 0}, {0, 1}}; // 单位矩阵 int[][] base = matrix; while (n > 0) { if ((n & 1) == 1) { result = matrixMultiply(result, base); } base = matrixMultiply(base, base); n >>= 1; } return result; } private int[][] matrixMultiply(int[][] a, int[][] b) { int[][] c = new int[2][2]; c[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0]; c[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1]; c[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0]; c[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1]; return c; }复杂度分析
时间复杂度：O(log n) — 快速幂
空间复杂度：O(1)
优缺点
✅ 时间复杂度最优 O(log n)
✅ 没有浮点数精度问题
❌ 代码复杂，面试不常用
方法对比总结
| 方法 | 时间复杂度 | 空间复杂度 | 难度 | 推荐度 |
|---|---|---|---|---|
| 递归 | O(2ⁿ) | O(n) | 简单 | ⭐ |
| 递归+记忆化 | O(n) | O(n) | 中等 | ⭐⭐⭐ |
| DP数组 | O(n) | O(n) | 简单 | ⭐⭐⭐ |
| 滚动数组 | O(n) | O(1) | 简单 | ⭐⭐⭐⭐⭐ |
| 通项公式 | O(log n) | O(1) | 较难 | ⭐⭐ |
| 矩阵快速幂 | O(log n) | O(1) | 难 | ⭐⭐ |
图文详解
爬楼梯的递归树（n=5）
text
climb(5) / \ climb(4) climb(3) / \ / \ climb(3) climb(2) climb(2) climb(1) / \ | | | climb(2) climb(1) 2 2 1 | | 2 1 结果 = 8
动态规划状态转移图
text
第1阶: 1种方法 第2阶: 2种方法 第3阶 = 第2阶 + 第1阶 = 2 + 1 = 3种 第4阶 = 第3阶 + 第2阶 = 3 + 2 = 5种 第5阶 = 第4阶 + 第3阶 = 5 + 3 = 8种 可视化： 台阶: 1 2 3 4 5 方法数: 1 → 2 → 3 → 5 → 8 └─加─┘ └─加─┘
路径枚举（n=4，共5种）
text
1. 1 + 1 + 1 + 1 2. 1 + 1 + 2 3. 1 + 2 + 1 4. 2 + 1 + 1 5. 2 + 2
常见问题 Q&A
Q1：为什么是斐波那契数列？
A：因为到达第 i 阶只有两种途径：
从第 i-1 阶爬 1 阶
从第 i-2 阶爬 2 阶
所以f(i) = f(i-1) + f(i-2)，这正是斐波那契递推公式。
Q2：边界条件为什么是 dp[1]=1, dp[2]=2？
A：
1 阶：只能爬 1 阶 → 1 种
2 阶：可以 1+1 或 2 → 2 种
注意这和标准斐波那契（1,1,2,3,5...）不同，这里是（1,2,3,5,8...），实际上是斐波那契偏移了一位。
Q3：n=0 时需要处理吗？
A：题目约束n >= 1，不需要处理。但如果扩展，dp[0]=1（有一种方法：不动）也能让递推成立。
Q4：为什么滚动数组可以优化空间？
A：因为计算dp[i]只需要dp[i-1]和dp[i-2]，不需要保留整个数组。
Q5：n=45 时结果会溢出吗？
A：不会。climbStairs(45) = 1836311903，小于int最大值2^31-1 = 2147483647。
扩展思考
变体1：每次可以爬 1, 2, 3 个台阶
java
public int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; if (n == 3) return 4; int prev3 = 1, prev2 = 2, prev1 = 4; for (int i = 4; i <= n; i++) { int current = prev1 + prev2 + prev3; prev3 = prev2; prev2 = prev1; prev1 = current; } return prev1; }变体2：每次可以爬 1 或 2 个台阶，但不能连续爬 2 个台阶
这需要增加状态维度来记录上一步是爬了 1 阶还是 2 阶。
总结
爬楼梯是 LeetCode Hot 100 中最经典的动态规划入门题，也是斐波那契数列的典型应用。
面试建议：
先说递归解法（展示思路）
指出递归的问题（重复计算），引出记忆化搜索
给出 DP 数组解法
最后优化到滚动数组（O(1) 空间）
如果面试官追问，可以提一下矩阵快速幂
核心要点：
理解状态转移方程
dp[i] = dp[i-1] + dp[i-2]掌握空间优化技巧（滚动数组）
能够手推小规模数据验证
一句话总结：
爬到第 n 阶的方法数 = 爬到第 n-1 阶的方法数（再爬 1 阶）+ 爬到第 n-2 阶的方法数（再爬 2 阶）
参考链接
LeetCode 70. 爬楼梯 题目链接
LeetCode 70. 爬楼梯 官方题解