C語言陣列實作費波納契數列：空間換時間的動態規劃雛形

使用陣列儲存費波納契數列中間結果，是動態規劃「自底向上」思想的典型體現。此法不僅避免遞歸重複計算，更能隨時存取任意項數值，適用於需多次查詢或輸出完整數列的場景。

陣列實作完整程式碼

#include <stdio.h>
#define MAX_SIZE 100

int main() {
    int i, n;
    int fib[MAX_SIZE] = {0, 1, 1};  // 索引 0 不用，1、2 初始化為 1

    printf("請輸入項數 n (1-%d): ", MAX_SIZE-1);
    scanf("%d", &n);

    if (n < 1 || n >= MAX_SIZE) {
        printf("輸入超出範圍\n");
        return 1;
    }

    for (i = 3; i <= n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }

    printf("第 %d 項: %d\n", n, fib[n]);
    printf("前 %d 項完整數列: ", n);
    for (i = 1; i <= n; i++) {
        printf("%d ", fib[i]);
    }
    printf("\n");
    return 0;
}

核心設計考量

陣列索引對應策略

採用 fib[1]=1, fib[2]=1 對應數學定義，fib[0] 棄用，使索引與項數直觀對應，減少心智負擔。

空間複雜度權衡

• 優點：O(1) 存取任意已計算項，支援完整數列輸出
• 缺點：O(n) 空間，n 極大時記憶體壓力大
• 改進：滾動陣列 fib[3] 可壓縮至 O(1) 空間

動態規劃視角解析

此解法完美展示動態規劃三要素：

1. 最優子結構：F(n) 由 F(n-1)、F(n-2) 最優解構成
2. 重疊子問題：陣列消除遞歸中的重複計算
3. 狀態轉移方程：fib[i] = fib[i-1] + fib[i-2]

進階應用場景

多次查詢優化

預先計算前 N 項存入陣列，後續查詢 O(1) 回應，適合線上判題系統多測資案例。

矩陣快速冪輔助

陣列儲存冪次矩陣，配合二進制分解加速大 n 計算。

大數費波納契

// 使用字串陣列模擬大數加法
char fib[1000][1000];  // 每項最多 1000 位數字
// 實作字串加法函數 big_add(char* a, char* b, char* result)

三種解法效能實測對比 (n=40)

最佳實踐建議

• 單次查詢、大 n：三變數迭代或矩陣快速冪
• 多次查詢、需完整數列：陣列預計算
• 記憶體受限嵌入式：滾動陣列 int fib[3]
• 超大數值：大數加法 + 陣列/向量儲存

陣列版費波納契雖非極致空間優化，但其清晰的狀態轉移邏輯與隨機存取能力，使其成為動態規劃入門的最佳範例，也是許多複雜 DP 問題的基礎範本。