70. 爬楼梯 Easy

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1:
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶： 1 阶 + 1 阶 或 2 阶

示例 2:
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶：1 阶 + 1 阶 + 1 阶 或 1 阶 + 2 阶 或 2 阶 + 1 阶

解题思路

输入： 有 n 个台阶

输出： 每次可以爬 1 或 2 个台阶，可以有多少种不同的方法爬到楼顶

本题属于线性DP问题。有时也叫 斐波那契型 DP 或 一维 DP。

我们可以设想一下，假如只剩下 1 个台阶，那就只会有 1 种方法 dp[1] = 1

如果只剩下 2 个台阶，那就只会有 2 种方法 dp[2] = 1

如果剩下了 3 个台阶，那就是 1 + 2 = 3 种方法 dp[3] = dp[1] + dp[2]

以此类推那么想要知道剩下 n 个台阶有多少种就是 dp[n] = dp[n - 2] + dp[n - 1]

我们可以有递归和循环两种实现方式，注意递归的实现方案需要做一下缓存减少重复计算并防止爆栈

代码实现

python

class Solution:
    def climbStairs(self, n: int) -> int:
        # 特殊情况处理：如果楼梯层数 <= 2，返回 n 本身
        if n <= 2:
            return n

        # 方法一：动态规划（自底向上）
        # 创建一个长度为 n+1 的数组来保存每一阶的走法数
        dp = [0] * (n + 1)

        # 初始化前两个台阶的走法
        dp[1] = 1  # 只有一级台阶时，只有一种走法
        dp[2] = 2  # 两级台阶，有两种走法：1+1 或直接2

        # 从第3级开始，每一级的走法 = 前一阶 + 前两阶
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        # 返回第n级台阶的总走法
        return dp[n]

javascript

/**
 * @param {number} n
 * @return {number}
 */
const climbStairs = function(n) {
    if (n <= 2) return n;

    const dp = Array(n + 1).fill(0);

    dp[1] = 1;
    dp[2] = 2;

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

    return dp[n];
};

python

class Solution:
    def climbStairs(self, n: int) -> int:
        # 方法二：记忆化递归（自顶向下）
        # 使用 @cache 自动缓存已计算的结果，避免重复计算
        @cache
        def dp(i):
            # 如果是第1级或第2级，返回走法数就是 i 本身
            if i <= 2:
                return i

            # 否则，递归计算 dp(i-1) 和 dp(i-2)
            return dp(i - 1) + dp(i - 2)

        # 调用记忆化递归函数返回结果
        return dp(n)

javascript

/**
 * @param {number} n
 * @return {number}
 */
const climbStairs = function(n) {
    const cache = {};

    function dp(i) {
        if (i <= 2) return i;

        if (cache[i]) return cache[i];

        const res = dp(i - 1) + dp(i - 2);

        cache[i] = res;

        return cache[i];
    }

    return dp(n);
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

70 国际版

70 中文版