0070.爬楼梯

难度：🟢 简单

标签：动态规划、记忆化搜索、数学

链接：70. 爬楼梯

题目描述

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

解题思路

核心思想

本题是一道非常经典的 动态规划 (Dynamic Programming) 入门题。问题的核心在于，要想到达第 n 阶楼梯，只有两种可能的方式：

1. 从第 n-1 阶爬 1 个台阶上来。

2. 从第 n-2 阶爬 2 个台阶上来。

因此，到达第 n 阶的方法总数，就是到达第 n-1 阶的方法数与到达第 n-2 阶的方法数之和。这恰好是斐波那契数列的定义。

思路选择

动态规划（空间优化） 是解决此问题的最优思路。

• 我们可以定义 dp[i] 为到达第 i 阶的方法数，那么状态转移方程就是 dp[i] = dp[i-1] + dp[i-2]。

• 进一步观察可以发现，计算 dp[i] 时，我们只需要 dp[i-1] 和 dp[i-2] 的值。因此，没有必要创建一个完整的 dp 数组，只需用两个变量来滚动记录前两个状态的值即可，从而将空间复杂度从 O(n) 优化到 O(1)。

关键步骤

1. 处理边界情况：当 n <= 2 时，方法数就等于 n，直接返回。

2. 初始化：初始化两个变量 first = 1（代表到达第 1 阶的方法数）和 second = 2（代表到达第 2 阶的方法数）。

3. 循环迭代：从 i = 3 开始循环到 n。 a. 在循环中，计算到达第 i 阶的方法数 temp = first + second。 b. 更新状态：将 first 更新为原来的 second，将 second 更新为 temp，为计算下一阶做准备。这个过程被称为“滚动数组”。

4. 返回结果：循环结束后，second 变量中存储的就是到达第 n 阶的方法总数，返回 second。

代码实现

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    // 处理 n=1 和 n=2 的基本情况
    if (n <= 2) {
        return n;
    }

    // 初始化前两个状态
    let first = 1; // 到达第1阶的方法数
    let second = 2; // 到达第2阶的方法数

    // 从第3阶开始迭代
    for (let i = 3; i <= n; i++) {
        // 当前阶的方法数是前两阶之和
        let temp = first + second;
        // 滚动更新状态
        first = second;
        second = temp;
    }

    // 返回最终结果
    return second;
};

复杂度分析

• 时间复杂度：O(n) 我们只需要一个从 3 到 n 的循环，循环次数与 n 成正比。

• 空间复杂度：O(1) 我们只使用了 first, second, temp 等常数个变量，与输入 n 的大小无关。

相关题目

• 0509.斐波那契数

• 0746.使用最小花费爬楼梯

• 0198.打家劫舍

总结

本题是动态规划思想的绝佳入门案例，它清晰地展示了如何找出状态转移方程，并在此基础上进行求解。从朴素递归到记忆化搜索，再到动态规划，最后通过“滚动数组”思想进行空间优化，完整地体现了算法优化的过程，是学习者必须掌握的经典模型。