Fibonacci (Tablolama)

Dinamik Programlama O(n) O(n)

Fibonacci dizisini aşağıdan yukarıya kurar; her terim kendinden önceki ikinin toplamıdır — tekrar iş yok.

i	0	1	2	3	4	5	6	7	8
fib	0	·	·	·	·	·	·	·	·

1/10

Taban durum: dp[0] = 0.

Değişmezdp[i] yazıldığı anda nihaidir; her alt problem tam bir kez çözülür — üstel patlamayı kaldıran budur.

hesaplanıyorokuduğudolu

fibonacci.c

int fib(int n) {
    if (n <= 1) return n;
    int dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

Fibonacci (Tablolama) nasıl çalışır?

Diziyi tabloda aşağıdan yukarı kur: her giriş önceki ikisinin toplamı. Tablolama, üstel özyineleme ağacını tek doğrusal taramaya çevirir.

Ne zaman kullanılır?

DP'nin 'hello world'ü — asıl aktarılan, örtüşen alt problemleri hafızalama desenidir.