爬楼梯

LeetCode 官方题目链接

题目描述

假设你正在爬楼梯。需要 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. 定义状态：dp[i] 表示爬到第 i 阶楼梯的方法数。
2. 状态转移方程：
   • 要到达第 i 阶，只能从第 i-1 阶爬 1 步上来，或者从第 i-2 阶爬 2 步上来。
   • 所以 dp[i] = dp[i-1] + dp[i-2]。
3. 初始条件：
   • dp[1] = 1 （只有一种方法：1步）
   • dp[2] = 2 （两种方法：1+1 或 2）

这其实就是斐波那契数列。

空间优化

我们发现 dp[i] 只依赖于 dp[i-1] 和 dp[i-2]，所以不需要维护整个数组，只需要维护两个变量即可，将空间复杂度从 $O(n)$ 降到 $O(1)$。

代码实现

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n <= 2) return n;
    
    let prev2 = 1; // dp[i-2]
    let prev1 = 2; // dp[i-1]
    
    for (let i = 3; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
};

运行演示

假设 n = 5：

1. 初始化: prev2 = 1 (dp[1]), prev1 = 2 (dp[2])
2. i = 3: current = 2 + 1 = 3, prev2 = 2, prev1 = 3
3. i = 4: current = 3 + 2 = 5, prev2 = 3, prev1 = 5
4. i = 5: current = 5 + 3 = 8, prev2 = 5, prev1 = 8

返回 8。

复杂度分析

• 时间复杂度：$O(n)$，循环执行 n 次。
• 空间复杂度：$O(1)$，只使用了常数个变量。