LeetCode 70：爬樓梯——斐波那契數列的多種解法與通項公式

題目描述

n 階樓梯，每次可爬 1 或 2 階。求到達頂部的不同方法數。f(n) = f(n-1) + f(n-2)，f(1)=1, f(2)=2。

解法一：迭代 O(n) 時間 O(1) 空間

int climbStairs(int n) {
    int a = 1, b = 1;  // f(0)=1, f(1)=1
    for (int i = 2; i <= n; ++i) {
        int c = a + b;
        a = b; b = c;
    }
    return b;
}

解法二：通項公式 O(1) 時間（Binet 公式）

f(n) = (φ^(n+1) - ψ^(n+1)) / √5，其中 φ = (1+√5)/2, ψ = (1-√5)/2。

int climbStairs(int n) {
    const double sqrt5 = sqrt(5);
    double phi = (1 + sqrt5) / 2;
    double psi = (1 - sqrt5) / 2;
    return (int)round((pow(phi, n+1) - pow(psi, n+1)) / sqrt5);
}

注意：浮點精度在 n > 70 時可能誤差，競賽中首選迭代或矩陣快速冪。

解法三：矩陣快速冪 O(log n)

[f(n), f(n-1)]^T = M^(n-1) * [1, 1]^T，M = [[1,1],[1,0]]。利用二進制快速冪計算矩陣冪。

總結

爬樓梯本質是斐波那契數列。工程實踐推薦迭代法（簡單、精確、無溢位風險）；追求極致時間複雜度可用矩陣快速冪；通項公式適合數學分析與小 n 場景。