爬楼梯问题

问题

假设你正在爬楼梯，需要 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 <= n <= 45

解答

方法一：动态规划（滚动数组优化）

用 f(x) 表示爬到第 x 级台阶的方案数。因为每次只能爬 1 或 2 级，所以到达第 x 级只能从第 x-1 级或第 x-2 级转移过来，得到递推关系：

f(x) = f(x-1) + f(x-2)

边界条件：f(0) = 1，f(1) = 1

由于 f(x) 只依赖前两项，可以用滚动数组将空间复杂度优化到 O(1)：

var climbStairs = function(n) {
    let p = 0, q = 0, r = 1;
    for (let i = 1; i <= n; ++i) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
};

复杂度分析：

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

方法二：通项公式

这个递推数列实际上是斐波那契数列。根据递推方程可以写出特征方程 x² = x + 1，求解得到通项公式：

var climbStairs = function(n) {
    const sqrt5 = Math.sqrt(5);
    const fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
    return Math.round(fibn / sqrt5);
};

复杂度分析： 取决于 pow 函数的实现，通常可以认为是 O(log n)

关键点

• 问题本质是斐波那契数列，f(n) = f(n-1) + f(n-2)
• 边界条件设置为 f(0) = 1, f(1) = 1
• 使用滚动数组优化空间复杂度到 O(1)，只保留前两项的值
• 对于更大的 n，可以使用矩阵快速幂优化到 O(log n) 或直接使用通项公式
• 通项公式使用浮点数计算可能存在精度误差，需要四舍五入