爬楼梯

题目描述

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

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

示例

示例 1：

输入: n = 2
输出: 2
解释: 有两种方法：① 1阶+1阶  ② 2阶

示例 2：

输入: n = 3
输出: 3
解释: 有三种方法：① 1+1+1  ② 1+2  ③ 2+1

示例 3：

输入: n = 4
输出: 5
解释: 有五种方法：1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2

示例 4：

输入: n = 1
输出: 1

解题思路

本质是斐波那契数列问题。

当我们站在第 i 阶时，上一步要么从第 i-1 阶跨 1 步，要么从第 i-2 阶跨 2 步。因此：

状态定义：dp[i] = 爬到第 i 阶的方法数

状态转移方程：dp[i] = dp[i-1] + dp[i-2]

初始状态：dp[1] = 1，dp[2] = 2

空间优化：由于 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，可以用两个滚动变量代替整个数组，将空间复杂度降为 O(1)。

代码实现

/**
 * 方法一：基础 DP 数组版
 * @param {number} n - 楼梯阶数
 * @returns {number} 不同爬法总数
 */
function climbStairs(n) {
    if (n <= 2) return n;
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

/**
 * 方法二：空间优化版（仅用两个变量）
 * @param {number} n - 楼梯阶数
 * @returns {number} 不同爬法总数
 */
function climbStairsOptimized(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 cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

复杂度分析

• 时间复杂度：O(n)，一次遍历。
• 空间复杂度：DP 数组版 O(n)；滚动变量版 O(1)。

n = 3

3