LeetCode 爬樓梯：費波那契數列的動態規劃與矩陣快速冪解法

問題與遞推

每步可爬 1 或 2 階，求爬 n 階的方法數。
f(n) = f(n-1) + f(n-2)，f(1)=1, f(2)=2。即費波那契數列後移一位。

O(n) 迭代法（滾動變量）

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

O(log n) 矩陣快速冪

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

通項公式（Binet 公式，雙精度誤差風險）

f(n) = round(φ^n / √5)，φ = (1+√5)/2。n ≤ 45 時 double 精度足夠。

擴展：k 步爬樓梯

若每步可爬 1..k 階，則 f(n) = sum_{i=1..k} f(n-i)，用滑動窗口 O(n) 或矩陣 O(k^3 log n) 求解。

複雜度總結