题目描述：
假设你正在爬楼梯。需要
n阶你才能到达楼顶。每次你可以爬
1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：
输入：n = 2输出：2解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：
输入：n = 3输出：3解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
解题思路：
方法一：动态规划
核心思路：
状态定义：
dp[i]= 爬到第i阶的方法数。
状态转移：
要到达第i阶，可以从：
第
i-1阶爬 1 阶上来第
i-2阶爬 2 阶上来
dp[i] = dp[i-1] + dp[i-2]
初始化：
dp[0] = 1（地面，1 种方法）dp[1] = 1（爬 1 阶，1 种方法）
具体过程示例：
n = 5
| i | dp[i] |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
结果：8✅
代码实现：
写法1：数组 DP
class Solution { public: int climbStairs(int n) { if (n <= 1) return 1; vector<int> dp(n + 1, 0); dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } };写法2：滚动变量（空间优化）
class Solution { public: int climbStairs(int n) { if (n <= 1) return 1; int prev2 = 1; // dp[0] int prev1 = 1; // dp[1] for (int i = 2; i <= n; i++) { int curr = prev1 + prev2; prev2 = prev1; prev1 = curr; } return prev1; } };写法3：通项公式（斐波那契）
class Solution { public: int climbStairs(int n) { double sqrt5 = sqrt(5); double fib = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1); return round(fib / sqrt5); } };注意：浮点数精度问题，n 很大时可能出错。
复杂度分析：
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 数组 DP | O(n) | O(n) |
| 滚动变量 | O(n) | O(1) |
| 通项公式 | O(log n) | O(1) |
关键细节：
1. 为什么是斐波那契数列？
dp[i] = dp[i-1] + dp[i-2]正是斐波那契的递推公式。
dp[1] = 1dp[2] = 2dp[3] = 3dp[4] = 5dp[5] = 8
2. 为什么dp[0] = 1？
地面可以看作"爬 0 阶"，有 1 种方法（什么都不做）。
3. 和「斐波那契数」的区别
| 题目 | 区别 |
|---|---|
| 509. 斐波那契数 | F(0)=0, F(1)=1 |
| 70. 爬楼梯 | dp[0]=1, dp[1]=1 |
本质一样，只是初始值不同。
4. 如果每次可以爬 1、2、3 阶呢？
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，类似「三步问题」。
方法二：递归 + 记忆化
代码实现：
class Solution { public: int climbStairs(int n) { vector<int> memo(n + 1, -1); return dfs(n, memo); } private: int dfs(int n, vector<int>& memo) { if (n <= 1) return 1; if (memo[n] != -1) return memo[n]; memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo); return memo[n]; } };复杂度：时间 O(n)，空间 O(n)
方法三：矩阵快速幂（O(log n)）
代码实现：
class Solution { public: int climbStairs(int n) { if (n <= 1) return 1; vector<vector<long long>> M = {{1, 1}, {1, 0}}; vector<vector<long long>> result = matrixPow(M, n); return result[0][0]; } private: vector<vector<long long>> matrixPow(vector<vector<long long>>& M, int n) { vector<vector<long long>> result = {{1, 0}, {0, 1}}; vector<vector<long long>> base = M; while (n > 0) { if (n & 1) result = multiply(result, base); base = multiply(base, base); n >>= 1; } return result; } vector<vector<long long>> multiply(vector<vector<long long>>& A, vector<vector<long long>>& B) { vector<vector<long long>> C(2, vector<long long>(2, 0)); for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { C[i][j] += A[i][k] * B[k][j]; } } } return C; } };复杂度：时间 O(log n)，空间 O(1)
四种方法对比：
| 方法 | 时间复杂度 | 空间复杂度 | 推荐度 |
|---|---|---|---|
| 滚动变量 DP | O(n) | O(1) | ⭐⭐⭐⭐⭐ |
| 数组 DP | O(n) | O(n) | ⭐⭐⭐⭐ |
| 矩阵快速幂 | O(log n) | O(1) | ⭐⭐⭐ |
| 通项公式 | O(log n) | O(1) | ⭐⭐ |
总结：
| 要点 | 说明 |
|---|---|
| 核心思想 | dp[i] = dp[i-1] + dp[i-2] |
| 初始化 | dp[0] = 1，dp[1] = 1 |
| 时间复杂度 | O(n) |
| 空间复杂度 | O(1)（滚动变量） |
