爬楼梯

假设你正在爬楼梯。需要 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

解法一（动态规划）：

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2)
        {
            return n;
        }

        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
};

解法二（滚动变量优化）：

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2)
        {
            return n;
        }

        int prev2 = 1;
        int prev1 = 2;
        int cur = 0;

        for (int i = 3; i <= n; i++)
        {
            cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }

        return prev1;
    }
};

核心思想

这题本质上是一个动态规划问题。

因为要到达第 n 阶，最后一步只有两种可能：

1. 从第 n - 1 阶爬 1 阶上来。
2. 从第 n - 2 阶爬 2 阶上来。

除此之外没有其他方式。

所以，到达第 n 阶的方法数，等于：

• 到达第 n - 1 阶的方法数
• 加上到达第 n - 2 阶的方法数

这就形成了递推关系。

状态定义

定义：

dp[i] 表示爬到第 i 阶楼梯的方法数。

那么题目要求的答案就是：

dp[n]

递推公式推导

考虑如何到达第 i 阶。

因为每次只能爬 1 或 2 个台阶，所以最后一步只有两种情况。

1. 最后一步爬 1 阶

如果最后一步爬 1 阶，那么上一步一定在第 i - 1 阶。

到达第 i - 1 阶的方法数是：

dp[i - 1]

这些方法后面都可以再接一步 1 阶，到达第 i 阶。

所以这一类方法有：

dp[i - 1]

种。

2. 最后一步爬 2 阶

如果最后一步爬 2 阶，那么上一步一定在第 i - 2 阶。

到达第 i - 2 阶的方法数是：

dp[i - 2]

这些方法后面都可以再接一步 2 阶，到达第 i 阶。

所以这一类方法有：

dp[i - 2]

种。

两类方法的最后一步不同，所以它们不会重复。

因此：

dp[i] = dp[i - 1] + dp[i - 2]

这就是状态转移公式。

边界情况

当 n = 1 时，只有一种方法：

1

所以：

dp[1] = 1

当 n = 2 时，有两种方法：

• 1 + 1
• 2

所以：

dp[2] = 2

之后就可以从 3 开始递推。

为什么可以用滚动变量优化

从递推公式可以看到：

dp[i] = dp[i - 1] + dp[i - 2]

计算当前状态 dp[i] 时，只需要前两个状态：

• dp[i - 1]
• dp[i - 2]

不需要更早的 dp[i - 3]、dp[i - 4] 等状态。

所以可以不用数组，只用两个变量保存前两个状态：

• prev2 表示 dp[i - 2]
• prev1 表示 dp[i - 1]

每次计算：

cur = prev1 + prev2;

然后向后滚动：

prev2 = prev1;
prev1 = cur;

这样就把空间复杂度从 O(n) 优化到了 O(1)。

正确性证明

我们证明动态规划算法返回的 dp[n] 是爬到第 n 阶的方法数。

归纳基

当 i = 1 时，只有一种方法：爬 1 阶。

所以 dp[1] = 1 正确。

当 i = 2 时，有两种方法：

• 1 + 1
• 2

所以 dp[2] = 2 正确。

归纳假设

假设对于所有小于 i 的台阶数，dp 都能正确表示爬到该台阶的方法数。

也就是说，dp[i - 1] 和 dp[i - 2] 都是正确的。

归纳推导

现在考虑第 i 阶。

爬到第 i 阶的最后一步只能是：

• 从第 i - 1 阶爬 1 阶
• 从第 i - 2 阶爬 2 阶

根据归纳假设，到达第 i - 1 阶的方法数是 dp[i - 1]，到达第 i - 2 阶的方法数是 dp[i - 2]。

这两类方法的最后一步不同，因此互不重复。

同时，任意一种到达第 i 阶的方法，最后一步也一定属于这两类之一，因此不会漏掉。

所以：

dp[i] = dp[i - 1] + dp[i - 2]

正确。

由数学归纳法可知，最终 dp[n] 正确。

滚动变量解法只是把数组中的前两个状态用变量保存，递推逻辑完全相同，因此同样正确。

举例理解

以 n = 5 为例：

• dp[1] = 1
• dp[2] = 2
• dp[3] = dp[2] + dp[1] = 3
• dp[4] = dp[3] + dp[2] = 5
• dp[5] = dp[4] + dp[3] = 8

所以爬到第 5 阶一共有 8 种方法。

复杂度分析

解法一

• 需要从 3 遍历到 n
• 时间复杂度：O(n)
• 使用一个长度为 n + 1 的数组
• 空间复杂度：O(n)

解法二

• 同样只遍历一次
• 时间复杂度：O(n)
• 只使用常数个变量
• 空间复杂度：O(1)

如果只要求返回答案，推荐使用解法二。