LeetCode 70 爬樓梯：動態規劃與費波那契數列的完美邂逅

題目回顧

你正在爬一個需要 n 階才能到達頂部的樓梯。每次你可以爬 1 階或 2 階。請問有多少種不同的方法可以爬到樓頂？

核心洞察：這其實是費波那契數列

設 dp[i] 為到達第 i 階的方法數。最後一步只能從 i-1（跨 1 階）或 i-2（跨 2 階）到達，因此狀態轉移方程為：

dp[i] = dp[i-1] + dp[i-2]

邊界條件：dp[1] = 1，dp[2] = 2。這正是費波那契數列的變體（起始項為 1, 2）。

三種實現方案對比

1. 遞歸 + 備忘錄（自頂向下）

int climbStairs(int n) {
    vector<int> memo(n + 1, -1);
    function<int(int)> dfs = [&](int i) -> int {
        if (i <= 2) return i;
        if (memo[i] != -1) return memo[i];
        return memo[i] = dfs(i - 1) + dfs(i - 2);
    };
    return dfs(n);
}

時間複雜度 O(n)，空間複雜度 O(n)（遞歸棧 + 備忘錄）。

2. 迭代 DP（自底向上，優化空間）

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 b;
}

時間 O(n)，空間 O(1) —— 推薦寫法。

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

利用矩陣 [[1,1],[1,0]] 的 n-1 次方或 Binet 公式可進一步優化，適合極大 n（需注意精度）。

避坑提醒

• n=0 視為 1 種方法（原地不動），但題目通常 n >= 1。
• 結果可能溢出 32 位整數，LeetCode 測試範圍內 int 足夠，實際工程建議用 long long 或大整數庫。
• 別寫成 dp[i] = dp[i-1] + dp[i-2] + 1 這類常見筆誤。

舉一反三

同類問題：LeetCode 746 使用最小花費爬樓梯、青蛙跳台階、斐波那契數列變體。核心皆為「線性遞歸 + 狀態壓縮」。