Fibonacci adalah masalah DP paling sederhana yang menyentuh semua konsep inti: overlapping subproblems, optimal substructure, memoization, tabulation, dan optimasi ruang. Meski terlihat sepele, mempelajari Fibonacci secara mendalam memberi kita template mental untuk semua DP. Pada Chapter ini kita akan menelusuri empat versi implementasi — naif, memo, tabulation, dan space-optimized — sambil mengamati bagaimana setiap langkah memperbaiki kompleksitas.

Aturan: Recurrence Fibonacci #

Fibonacci didefinisikan sebagai:

  • fib(0) = 0, fib(1) = 1 (base case)
  • fib(n) = fib(n-1) + fib(n-2) untuk n > 1

Ini adalah recurrence linier orde 2 — setiap nilai bergantung pada dua nilai sebelumnya. Inilah yang membuatnya ideal untuk dipelajari: cukup kompleks untuk menunjukkan masalah overlapping subproblems, namun cukup sederhana untuk dianalisis penuh.

Mekanisme: Empat Tahap Optimasi #

Tahap 1 — Rekursi naif: implementasi langsung dari recurrence. Tidak ada caching. Kompleksitas waktu O(φ^n) ≈ O(1.618^n), ruang O(n) untuk call stack.

Tahap 2 — Memoization (top-down): tambahkan cache. Setiap sub-masalah dihitung sekali. Kompleksitas waktu O(n), ruang O(n).

Tahap 3 — Tabulation (bottom-up): bangun tabel iteratif. Hilangkan overhead rekursi. Kompleksitas waktu O(n), ruang O(n).

Tahap 4 — Space-optimized: bila hanya butuh dp[i-1] dan dp[i-2], ganti array dengan dua variabel. Kompleksitas waktu O(n), ruang O(1).

Kode: Empat Versi Fibonacci #

cpp 
#include <iostream>
#include <vector>
#include <chrono>

// Versi 1: rekursi naif
long long fib_naive(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib_naive(n - 1) + fib_naive(n - 2);
}

// Versi 2: memoization (top-down)
long long fib_memo(int n, std::vector<long long>& memo) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}

// Versi 3: tabulation (bottom-up)
long long fib_tabu(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    std::vector<long long> 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];
}

// Versi 4: space-optimized
long long fib_opt(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; ++i) {
        long long cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int main() {
    // Bandingkan hasil untuk n kecil
    int n = 40;
    std::vector<long long> memo(n + 1, -1);
    std::cout << "naif    fib(" << n << ") = " << fib_naive(n) << '\n';
    std::cout << "memo    fib(" << n << ") = " << fib_memo(n, memo) << '\n';
    std::cout << "tabu    fib(" << n << ") = " << fib_tabu(n) << '\n';
    std::cout << "opt     fib(" << n << ") = " << fib_opt(n) << '\n';

    // Versi cepat untuk n besar
    std::cout << "opt     fib(90) = " << fib_opt(90) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
naif    fib(40) = 102334155
memo    fib(40) = 102334155
tabu    fib(40) = 102334155
opt     fib(40) = 102334155
opt     fib(90) = 2880067194370816120
  1. Versi 1 (fib_naive): tidak ada cache. Memanggil fib(n-1) dan fib(n-2) secara rekursif. Untuk n=40, sekitar 331 juta panggilan — butuh detik.
  2. Versi 2 (fib_memo): cek memo[n] != -1 sebelum rekursi. Hanya 2n-1 panggilan rekursif unik.
  3. Versi 3 (fib_tabu): loop dari 2 hingga n, isi dp[i] = dp[i-1] + dp[i-2]. Tidak ada rekursi sama sekali.
  4. Versi 4 (fib_opt): hanya simpan prev1 dan prev2. Setiap iterasi geser jendela. Memori total: 16 byte (dua long long).

Tabel Kompleksitas #

VersiWaktuRuangCatatan
NaifO(φ^n)O(n) stackTidak praktis untuk n > 40
MemoizationO(n)O(n)Lazy evaluation
TabulationO(n)O(n)Cache-friendly
Space-optimizedO(n)O(1)Optimal untuk Fibonacci

Verifikasi Empirik: Jumlah Panggilan #

Mari kita ukur jumlah panggilan rekursif untuk naif vs memoization:

cpp 
#include <iostream>
#include <vector>

long long g_naive_calls = 0;
long long g_memo_calls = 0;

long long fib_naive(int n) {
    ++g_naive_calls;
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib_naive(n - 1) + fib_naive(n - 2);
}

long long fib_memo(int n, std::vector<long long>& memo) {
    ++g_memo_calls;
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}

int main() {
    for (int n : {10, 20, 30, 40}) {
        g_naive_calls = 0;
        fib_naive(n);
        std::vector<long long> memo(n + 1, -1);
        g_memo_calls = 0;
        fib_memo(n, memo);
        std::cout << "n=" << n
                  << " | naif: " << g_naive_calls << " panggilan"
                  << " | memo: " << g_memo_calls << " panggilan"
                  << " | rasio: " << (double)g_naive_calls / g_memo_calls
                  << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
n=10 | naif: 177 panggilan | memo: 19 panggilan | rasio: 9.31579
n=20 | naif: 21891 panggilan | memo: 39 panggilan | rasio: 561.308
n=30 | naif: 2692537 panggilan | memo: 59 panggilan | rasio: 45636.2
n=40 | naif: 331160281 panggilan | memo: 79 panggilan | rasio: 4.1919e+06
  1. Baris ++g_naive_calls;: counter global untuk setiap pemanggilan fungsi. Hanya untuk pengukuran, tidak untuk produksi.
  2. Pola naif: T(n) = T(n-1) + T(n-2) + 1 ≈ φ^n. Rasio pertumbuhan ~φ ≈ 1.618 per kenaikan n.
  3. Pola memo: 2n-1 panggilan. Setiap state dihitung sekali, ditambah overhead traversal.
  4. Rasio meledak: untuk n=40, naif melakukan 4 juta kali lebih banyak panggilan dibanding memo. Inilah kekuatan mengeliminasi recomputation.

Formulasi Matematika vs DP #

Pengamat mungkin bertanya: kenapa tidak pakai rumus Binet?

text 
fib(n) = (φ^n - (-φ)^(-n)) / √5

Rumus ini memberi O(1) secara teoritis. Namun:

  • Untuk n besar, presisi double atau long double tidak cukup. fib(80) sudah kehilangan akurasi signifikan.
  • Komputasi φ^n secara presisi butuh big-number arithmetic, yang bukan O(1).
  • DP tetap menjadi pilihan terbaik untuk hasil eksak.

Generalisasi: Linear Recurrence #

Fibonacci adalah kasus khusus dari linear recurrence orde k:

text 
a(n) = c1 * a(n-1) + c2 * a(n-2) + ... + ck * a(n-k)

DP dengan sliding window kompleksitas O(n·k) waktu, O(k) ruang. Untuk k besar dan n sangat besar, ada optimasi matrix exponentiation O(k³ · log n) yang akan dibahas di bab lanjutan.

Ringkasan #

  • Empat tahap optimasi Fibonacci: naif O(φ^n) → memo O(n)/O(n) → tabulation O(n)/O(n) → space-optimized O(n)/O(1).
  • Memoization menambahkan cache tanpa mengubah struktur kode.
  • Tabulation menghilangkan rekursi, lebih cepat secara empiris.
  • Space optimization bekerja bila transisi hanya butuh beberapa nilai terakhir.
  • Fibonacci adalah template mental untuk semua DP — kuasai ini sebelum lanjut ke masalah kompleks.