70. 爬楼梯 (Easy)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/climbing-stairs/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
假设你正在爬楼梯。需要 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
题目详细分析
- 数据范围：n <= 45，结果在 32 位整数范围内，不会溢出。
- 核心约束：每次只能走 1 步或 2 步，不能后退。这是典型的斐波那契数列结构。
- 边界条件：n = 1 时只有 1 种方法（走 1 步）；n = 2 时有 2 种方法（1+1 或 2）。
- 隐藏条件：楼梯问题本质是”排列”而非”组合”——因为 1+2 和 2+1 被视为不同的方法。
小白版直白理解
爬楼梯就像玩跳格子游戏——你站在第 0 阶，想跳到第 n 阶。每次你可以选择”跳 1 格”或”跳 2 格”。要计算跳到第 n 阶总共有多少种跳法，你会发现：跳到第 10 阶的方法数 = 跳到第 9 阶的方法数 + 跳到第 8 阶的方法数，因为从第 9 阶再跳 1 步就到，或者从第 8 阶跳 2 步就到。这其实就是斐波那契数列的规律。
解题思路
思路一：动态规划（推荐）
核心洞察：爬到第 i 阶的最后一步有两种可能——从第 i-1 阶走 1 步，或者从第 i-2 阶走 2 步。因此 dp[i] = dp[i-1] + dp[i-2]。
DP 五步法：
- dp 定义：
dp[i]表示爬到第 i 阶的方法数 - 递推公式：
dp[i] = dp[i-1] + dp[i-2] - 初始化：
dp[1] = 1（1 步到第 1 阶），dp[2] = 2（1+1 或 2） - 遍历顺序：从 i=3 到 n，正序
- 举例验证：n=4 → dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5 ✓
def climbStairs(n):
if n <= 2:
return n
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]思路二：空间优化 DP（滚动变量）
只用两个变量保存前两个状态，空间 O(1)。
def climbStairs(n):
if n <= 2:
return n
a, b = 1, 2 # a = dp[1], b = dp[2]
for _ in range(3, n + 1):
a, b = b, a + b # 滚动更新
return b思路三：斐波那契公式 / 矩阵快速幂
利用斐波那契通项公式或矩阵快速幂，可达到 O(log n) 时间。
def climbStairs(n):
sqrt5 = 5 ** 0.5
fib_n = ((1 + sqrt5) / 2) ** (n + 1) - ((1 - sqrt5) / 2) ** (n + 1)
return int(fib_n / sqrt5)易错点
- n 的范围：题目 n 从 1 开始，要处理 n=1 直接返回 1，不要访问 dp[2] 导致越界。
- 初始化值：
dp[0]在数学上有定义（dp[0]=1 表示空楼梯），但实际遍历中从 i=3 开始更直观。 - 结果溢出：虽然 n<=45 不会溢出，但大数场景需注意类型。
框架提炼
一维 DP 模板（斐波那契型）：
def linear_dp(n):
if n <= threshold:
return base_case
# 初始化前 k 个状态
dp = [0] * (n + 1)
dp[1] = init_val_1
dp[2] = init_val_2
for i in range(3, n + 1):
dp[i] = f(dp[i-1], dp[i-2], ...) # 递推关系
return dp[n]滚动变量优化模板：
def linear_dp_optimized(n):
if n <= threshold:
return base_case
a, b = init_vals
for _ in range(start, n + 1):
a, b = b, f(a, b)
return b