爬楼梯

解题思路

这个问题可以使用动态规划（Dynamic Programming, DP）来解决。每次你可以爬 1 个或 2 个台阶，这意味着到达第 n 阶的方法数是到达第 n-1 阶的方法数加上到达第 n-2 阶的方法数。这是因为你可以从 n-1 阶跨一步到达第 n 阶，或者从 n-2 阶跨两步到达第 n 阶。

动态规划解法

解法步骤：

1. 初始化一个数组 dp，其中 dp[i] 表示到达第 i 阶的方法数。
2. dp[0] 设为 1（虽然 0 阶没有实际意义，但设为 1 便于计算）。
3. dp[1] 设为 1（到达第 1 阶只有一种方法）。
4. 对于 i 从 2 到 n，dp[i] = dp[i-1] + dp[i-2]。
5. 返回 dp[n]。

JavaScript 实现：

function climbStairs(n) {
    if (n <= 1) return 1;

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

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

    return dp[n];
}

// 示例
console.log(climbStairs(2));  // 输出: 2
console.log(climbStairs(3));  // 输出: 3
console.log(climbStairs(4));  // 输出: 5

优化空间复杂度的解法

我们注意到，在计算 dp[i] 时，只需要用到 dp[i-1] 和 dp[i-2]，因此我们可以用两个变量来代替数组，从而将空间复杂度优化为 O(1)。

JavaScript 实现：

function climbStairs(n) {
    if (n <= 1) return 1;

    let prev2 = 1, prev1 = 1;

    for (let i = 2; i <= n; i++) {
        let current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

// 示例
console.log(climbStairs(2));  // 输出: 2
console.log(climbStairs(3));  // 输出: 3
console.log(climbStairs(4));  // 输出: 5

详细解答过程：

1. 如果 n 小于等于 1，直接返回 1，因为只有一种方法可以爬到楼顶。
2. 初始化两个变量 prev2 和 prev1，分别表示到达第 n-2 阶和第 n-1 阶的方法数。初始值都设为 1，因为 dp[0] 和 dp[1] 都是 1。
3. 从第 2 阶开始，循环到第 n 阶：
   • 计算当前阶的方法数 current，它是前两阶方法数之和。
   • 更新 prev2 为 prev1，prev1 为 current。
4. 最后返回 prev1，它表示到达第 n 阶的方法数。

优缺点分析：

优点：

• 时间复杂度为 O(n)，其中 n 是楼梯的阶数。每个阶数只计算一次。
• 空间复杂度为 O(1)，只使用了常数个额外的变量。

缺点：

• 无明显缺点，已经是最优解。

通过上述方法，可以高效地计算出爬到楼顶的不同方法数。