好的，我们这次来详细讲解 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 阶楼梯的不同方法数，并且每次只能走 1 阶或 2 阶。
这其实是一个经典的 动态规划（DP） 问题，也可以理解为 斐波那契数列 问题。

3. 思路分析

3.1 从简单情况入手

• 如果楼梯只有 1 阶：
  只有一种方法：爬 1 阶。
  所以 f(1) = 1。

• 如果楼梯有 2 阶：
  两种方法：
  1 阶 + 1 阶
  2 阶
  所以 f(2) = 2。

• 如果楼梯有 3 阶：
  我们考虑最后一步：

  • 如果最后一步是爬 1 阶，那么之前必须到达第 2 阶，而到达第 2 阶有 f(2) 种方法。
  • 如果最后一步是爬 2 阶，那么之前必须到达第 1 阶，而到达第 1 阶有 f(1) 种方法。
    所以 f(3) = f(2) + f(1) = 2 + 1 = 3。

3.2 发现递推规律

对于第 n 阶楼梯：

• 要到达第 n 阶，最后一步要么是从第 n-1 阶爬 1 阶上来，要么是从第 n-2 阶爬 2 阶上来。
• 因此，到达第 n 阶的方法数 = 到达第 n-1 阶的方法数 + 到达第 n-2 阶的方法数。

即：

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

并且初始条件：

\[f(1) = 1, \quad f(2) = 2 \]

注意：这个递推式和斐波那契数列很像，只是初始项不同（斐波那契是 f(1)=1, f(2)=1，这里是 f(1)=1, f(2)=2）。

4. 动态规划解法

我们可以用一个数组 dp 来存储中间结果，避免重复计算。

步骤：

1. 如果 n == 1，直接返回 1。
2. 如果 n == 2，直接返回 2。
3. 创建数组 dp，长度 n+1。
4. dp[1] = 1, dp[2] = 2。
5. 从 i = 3 到 n，计算 dp[i] = dp[i-1] + dp[i-2]。
6. 返回 dp[n]。

代码实现（Python）：

def climbStairs(n: int) -> int:
    if n == 1:
        return 1
    if n == 2:
        return 2
    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]

5. 空间优化

上面的方法需要 O(n) 的数组空间。
实际上，我们只需要前两个状态的值，所以可以用两个变量来迭代，将空间复杂度降到 O(1)。

优化步骤：

1. 如果 n == 1，返回 1。
2. 如果 n == 2，返回 2。
3. 初始化 prev1 = 1（表示到达第 1 阶的方法数），prev2 = 2（表示到达第 2 阶的方法数）。
4. 从 i = 3 到 n：
   • current = prev1 + prev2
   • prev1 = prev2
   • prev2 = current
5. 循环结束后，prev2 就是结果。

代码实现（Python）：

def climbStairs(n: int) -> int:
    if n == 1:
        return 1
    if n == 2:
        return 2
    prev1, prev2 = 1, 2
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev1, prev2 = prev2, current
    return prev2

6. 复杂度分析

• 时间复杂度：O(n)，只需一次循环到 n。
• 空间复杂度：O(1)，只用了常数个变量。

7. 总结

这道题的核心是发现 递推关系：
到达第 n 阶的方法数 = 到达第 n-1 阶的方法数 + 到达第 n-2 阶的方法数。
然后可以用动态规划（或理解为斐波那契数列）来高效求解，并且通过只保存前两个状态来优化空间。

这个思路是很多动态规划问题的入门经典，理解了它，对后续更复杂的 DP 问题（比如不同路径、打家劫舍等）会有很大帮助。