---
description: "按最后一步分类计数：到第 n 阶的走法 = 到 n-1 阶 + 到 n-2 阶，斐波那契，滚动两个变量"
---

# 70. 爬楼梯

LeetCode 70[^leetcode] · 简单 · 动态规划

## 题

爬 `n` 阶楼梯，每次可以上 1 阶或 2 阶，问有多少种不同的走法。

例：`n = 3` → `3`（1+1+1、1+2、2+1）。

## 一句话

最后一步要么是 1 阶、要么是 2 阶，两类不重不漏——`f(n) = f(n-1) + f(n-2)`。

## 关键技巧

**计数 DP 的标准动作：按最后一步分类。** 所有到达第 `n` 阶的走法，按最后一步分成两类：从 `n-1` 跨 1 阶上来、从 `n-2` 跨 2 阶上来。两类互斥且覆盖全部，所以方案数直接相加。

- 状态：$f(i)$ = 到达第 $i$ 阶的走法数。
- 转移：$f(i) = f(i-1) + f(i-2)$。
- 初值：$f(0) = 1$（站在地面，一种「什么都不做」的走法），$f(1) = 1$。
- 顺序：$i$ 从小到大。

**只依赖前两项就滚动。** 数组降成两个变量 `a, b`，空间 $O(1)$。

## 解

```python
class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1  # f(0), f(1)
        for _ in range(n - 1):
            a, b = b, a + b
        return b
```

时间 $O(n)$，空间 $O(1)$。

## 延伸

- **步长集合换成任意硬币**：就是「完全背包求排列数」——[322. 零钱兑换](0322-coin-change.md) 是它的最值版。
- **加限制**：不能连续走两次 2 阶、某些台阶坏了，都是给状态多加一维或给转移加条件。
- **更快**：斐波那契可用矩阵快速幂做到 $O(\log n)$，本题 `n ≤ 45` 用不上。

??? note "自测"

    ```python
    s = Solution()
    assert s.climbStairs(2) == 2
    assert s.climbStairs(3) == 3
    assert s.climbStairs(1) == 1
    assert s.climbStairs(45) == 1836311903
    ```

[^leetcode]: [LeetCode 70](https://leetcode.cn/problems/climbing-stairs/)，2026-09-29 读。