好的，我们这次来详细讲解 LeetCode 第 70 题「爬楼梯」。

1. 题目描述

题目：假设你正在爬楼梯。需要爬 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 阶

约束条件：1 <= n <= 45

2. 问题分析

我们先从小的 n 开始，手动列举一下，找规律。

• n = 1：只有 1 种方法（1 阶）
• n = 2：2 种方法（1+1、2）
• n = 3：3 种方法（1+1+1、1+2、2+1）
• n = 4：我们列举一下：
  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
    → 共 5 种方法。

我们观察结果序列：
n=1 → 1
n=2 → 2
n=3 → 3
n=4 → 5

这看起来像是 斐波那契数列：1, 2, 3, 5, 8, 13, ...（注意这里起始与标准斐波那契略有不同，标准是 1,1,2,3,5,...，这里是 1,2,3,5,...）

3. 为什么是斐波那契数列？

关键思路：
要到达第 n 阶楼梯，你最后一步只能是：

• 从第 n-1 阶跨 1 阶上来
• 从第 n-2 阶跨 2 阶上来

所以，到达第 n 阶的方法数 = 到达第 n-1 阶的方法数 + 到达第 n-2 阶的方法数。

即：

\[f(n) = f(n-1) + f(n-2) \]

其中：

• f(1) = 1
• f(2) = 2

这就是斐波那契的变种，只是初始值不同。

4. 解法一：递归（不推荐，但用于理解）

直接按公式递归：

def climbStairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climbStairs(n-1) + climbStairs(n-2)

缺点：
重复计算非常多，时间复杂度 O(2^n)，在 n 较大时（比如 45）会超慢。

5. 解法二：记忆化递归（自顶向下）

用一个数组（或字典）存储已经计算过的 f(k)，避免重复计算。

def climbStairs(n):
    memo = {}
    def helper(x):
        if x == 1:
            return 1
        if x == 2:
            return 2
        if x in memo:
            return memo[x]
        memo[x] = helper(x-1) + helper(x-2)
        return memo[x]
    return helper(n)

时间复杂度：O(n)
空间复杂度：O(n)（递归栈深度和 memo 空间）

6. 解法三：动态规划（自底向上，迭代）

用数组 dp 存储结果，dp[i] 表示到达第 i 阶的方法数。

def climbStairs(n):
    if n == 1:
        return 1
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

时间复杂度：O(n)
空间复杂度：O(n)（dp 数组）

7. 解法四：优化空间的动态规划

注意到 f(n) 只依赖于前两个状态，所以不需要整个数组，只用两个变量。

def climbStairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    first, second = 1, 2
    for i in range(3, n+1):
        third = first + second
        first, second = second, third
    return second

时间复杂度：O(n)
空间复杂度：O(1)

8. 解法五：矩阵快速幂（进阶，O(log n)）

斐波那契数列可以用矩阵快速幂在 O(log n) 时间内求解。

递推关系：

\[\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} f(n-1) \\ f(n-2) \end{bmatrix} \]

所以：

\[\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-2} \cdot \begin{bmatrix} f(2) \\ f(1) \end{bmatrix} \]

这里 f(2)=2, f(1)=1。

矩阵的幂可以用快速幂算法在 O(log n) 时间内计算。

代码（了解即可）：

def climbStairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    def matrix_mult(A, B):
        return [
            [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
            [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
        ]
    
    def matrix_power(M, power):
        result = [[1, 0], [0, 1]]
        while power:
            if power & 1:
                result = matrix_mult(result, M)
            M = matrix_mult(M, M)
            power >>= 1
        return result
    
    M = [[1, 1], [1, 0]]
    M_pow = matrix_power(M, n-2)
    # [f(n), f(n-1)]^T = M^(n-2) * [f(2), f(1)]^T
    return M_pow[0][0] * 2 + M_pow[0][1] * 1

9. 总结

• 核心思路：最后一步要么从 n-1 走 1 阶，要么从 n-2 走 2 阶，所以是斐波那契类问题。
• 最优常用解法：迭代法（O(n) 时间，O(1) 空间）。
• 进阶：矩阵快速幂（O(log n) 时间），适合 n 极大时（本题 n≤45，迭代足够）。

这个题是动态规划的入门经典，理解了它，对后续很多 DP 问题有帮助。