LeetCode 70. 爬楼梯

◎

本节目标

把到达每一阶的方案数拆成最后走一步或两步的互斥来源。

这是动态规划基础与线性状态中最小的计数母题。

题意与约束

每次可走一阶或两阶，求恰好到达第 n 阶的方案数。最后一步的长度把全部方案无重叠地分开。

第一反应与重复子问题

从第 n-1 阶走一步和从第 n-2 阶走两步都会到达终点，两个子问题反复出现，递归会重复计算。

状态定义与转移推导

令 dp[i] 为到达第 i 阶的方案数，则 dp[i] = dp[i-1] + dp[i-2]。初始 dp[1]=1、dp[2]=2。

正确性依据

任一合法走法按最后一步长度唯一归入上述两类；归纳假设两类子问题的计数正确，求和就恰好计数全部走法。

样例执行过程

n=5 时序列依次为 1, 2, 3, 5, 8，所以答案为 8。

代码实现

C++

C++17

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int previous = 1, current = 2;
        for (int step = 3; step <= n; step++) {
            int next = previous + current;
            previous = current;
            current = next;
        }
        return current;
    }
};

Python

Python 3

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        previous, current = 1, 2
        for _ in range(3, n + 1):
            previous, current = current, previous + current
        return current

复杂度分析

滚动两个前驱状态，时间 O(n)，额外空间 O(1)。

边界与易错点

• n=1 只有一种走法。
• 不要把两步和一步的顺序合并，它们代表不同走法。

模式迁移

当最后一次选择有多个固定来源时，仍可按最后一步分类；零钱计数和路径计数也常由此开始。