爬樓梯問題（斐波那契變體）：遞歸、迭代與動態規劃三種解法

問題描述

樓梯共 N 級（N ≥ 0）。每步可跨 1 級或 2 級。求從底到頂的不同走法總數。
輸入 N，若 N > 20 則取 N % 21（保證 0 ≤ N ≤ 20）。若取模後為 0，輸出 1。

數學建模：斐波那契數列

• F(0) = 1（原地算一種）
• F(1) = 1
• F(2) = 2 (1+1, 2)
• F(n) = F(n-1) + F(n-2) （n ≥ 3）
  最後一步來自 n-1 級（跨 1 級）或 n-2 級（跨 2 級）。

三種實現方案對比

1. 遞歸（指數級，極慢，僅教學用）

int climb_rec(int n) {
    if (n <= 1) return 1;
    return climb_rec(n-1) + climb_rec(n-2); // 大量重複計算
}

2. 迭代（O(n) 時間，O(1) 空間，推薦）

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

3. 遞歸 + 備忘錄（自頂向下動態規劃，O(n) 時間，O(n) 空間）

int memo[21] = {0};
int 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);
}

完整 AC 代碼（含取模邏輯）

#include 
int main() {
    int n;
    scanf("%d", &n);
    n %= 21;
    if (n == 0 || n == 1) { printf("1\n"); return 0; }
    int f0 = 1, f1 = 2; // F(1), F(2)
    for (int i = 3; i <= n; i++) {
        int tmp = f0 + f1;
        f0 = f1;
        f1 = tmp;
    }
    printf("%d\n", f1);
    return 0;
}

擴展思考

• 若每步可跨 1~M 級？ → F(n) = Σ F(n-i) (i=1..M)，滑動窗口優化。
• 矩陣快速冪可達 O(log n) 求第 N 項。
• 本質是**線性遞歸關係**，動態規劃經典入門模型。