演算法實作筆記：爬樓梯問題——費波那契數列的遞迴與動態規劃視角

問題描述

有 n 階樓梯，每步可跨 1 階或 2 階。求到達頂端的不同走法總數。例如：

• n=1：[1] → 1 種
• n=2：[1,1], [2] → 2 種
• n=3：[1,1,1], [1,2], [2,1] → 3 種

數學建模：遞迴關係

到達第 n 階的最後一步，必然來自第 n-1 階（跨 1 步）或第 n-2 階（跨 2 步）。兩者互斥且窮盡，故：

f(n) = f(n-1) + f(n-2)，且 f(1)=1, f(2)=2。

這正是費波那契數列的變體（標準費波那契 F(1)=1, F(2)=1，本題 f(n) = F(n+1)）。

方案一：遞迴列舉所有路徑（教學用）

若需列印每種具體走法（如 1 1 2），需用回溯法記錄路徑：

#define MAX_N 100
static int path[MAX_N];
static int top = 0;

void print_path(void) {
    for (int i = 0; i < top; ++i) printf("%d ", path[i]);
    putchar('\n');
}

void climb(int n) {
    if (n < 0) return;           // 超出範圍
    if (n == 0) { print_path(); return; }  // 正好到達

    // 選擇跨 1 步
    path[top++] = 1;
    climb(n - 1);
    --top;                       // 回溯

    // 選擇跨 2 步
    path[top++] = 2;
    climb(n - 2);
    --top;
}

複雜度：時間 O(2ⁿ)，空間 O(n)（遞迴棧 + 路徑陣列）。僅適合 n ≤ 20 教學演示。

方案二：僅求總數——動態規劃 / 迭代優化

遞迴有大量重疊子問題（如 f(3) 被重複計算）。自底向上迭代：

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

複雜度：時間 O(n)，空間 O(1)。可進一步用矩陣快速冪優化至 O(log n)。

方案三：記憶化遞迴

long long memo[1000] = {0};

long long climb_memo(int n) {
    if (n <= 1) return 1;
    if (memo[n]) return memo[n];
    return memo[n] = climb_memo(n-1) + climb_memo(n-2);
}

時間 O(n)，空間 O(n)，程式碼接近數學定義，適合遞迴思維較強的場景。

測試驗證

void test_climb(void) {
    assert(climb_ways(1) == 1);
    assert(climb_ways(2) == 2);
    assert(climb_ways(3) == 3);
    assert(climb_ways(4) == 5);
    assert(climb_ways(5) == 8);
    assert(climb_ways(10) == 89);
}

遞迴陷阱與測試策略

• 堆疊溢出：n > 10⁵ 時遞迴會爆棧，必須用迭代或尾遞迴優化（編譯器支援時）。
• 整數溢位：f(93) 超過 64 位有號整數範圍，大數需用大整數庫或取模。
• 測試順序：先測 n=1,2,3 等基礎情況，手算驗證；再測邊界 n=0、大數值；最後壓測效能。

延伸變體

1. 可跨 1~m 階：f(n) = Σ f(n-i), i=1..m，滑動窗口優化至 O(n)。
2. 部分台階損壞不可踩：DP 狀態增加「是否合法」判斷。
3. 最小步數/路徑權重：改為最短路徑問題，適用 BFS 或 Dijkstra。

總結

爬樓梯是「線性遞迴 → 動態規劃 → 矩陣快速冪」演進的完美教案。理解其最優子結構與重疊子問題特性，能舉一反三解決斐波那契、矩陣鏈乘法、編輯距離等經典 DP 問題。工程上：小 n 列舉路徑用回溯，大 n 求計數用迭代/快速冪。