LeetCode 70. 爬樓梯：斐波那契數列與動態規劃

LeetCode 70. 爬樓梯

題目描述

爬 n 階樓梯，每步可爬 1 或 2 階。求到達頂部的不同方法數。

遞推關係：斐波那契數列

• dp[1] = 1（1 階：1 種）
• dp[2] = 2（2 階：1+1, 2）
• dp[n] = dp[n-1] + dp[n-2]（最後一步來自 n-1 或 n-2 階）

即 dp[n] = Fib(n+1)。

遞歸超時問題

直接遞歸 climb(n) = climb(n-1) + climb(n-2) 存在大量重複子問題，n=44 時指數級爆炸，會超時。

迭代 O(1) 空間解法

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

矩陣快速冪 / 通項公式（O(log n)）

斐波那契數列可用矩陣冪加速：

[F(n+1)]   [1 1]^n   [1]
[F(n)  ] = [1 0]    * [0]

或 Binet 公式：F(n) = (φ^n - ψ^n) / √5（φ=(1+√5)/2，ψ=(1-√5)/2），需注意浮點精度。

複雜度分析

• 迭代法：時間 O(n)，空間 O(1)。
• 矩陣快速冪：時間 O(log n)，空間 O(1)。

總結

爬樓梯是動態規劃入門經典，本質是斐波那契數列。掌握「狀態轉移方程 → 迭代優化空間 → 矩陣快速冪優化時間」的進階路徑，可應對所有線性遞推問題。