70. 爬楼梯

LeetCode 70¹ · 简单 · 动态规划

题

爬 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)\)。

解

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. 零钱兑换 是它的最值版。
• 加限制：不能连续走两次 2 阶、某些台阶坏了，都是给状态多加一维或给转移加条件。
• 更快：斐波那契可用矩阵快速幂做到 \(O(\log n)\)，本题 n ≤ 45 用不上。

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