Tabulation

Tabulation adalah pendekatan DP bottom-up di mana kita membangun tabel solusi secara iteratif mulai dari sub-masalah terkecil hingga masalah utama. Berbeda dengan memoization yang mengevaluasi sub-masalah saat dibutuhkan, tabulation menghitung semua sub-masalah dalam urutan tertentu. Pendekatan ini menghilangkan overhead rekursi dan seringkali lebih cepat secara empiris. Pada Chapter ini kita akan membedah mekanisme tabulation, urutan pengisian tabel, optimasi ruang, serta kapan tabulation lebih unggul dibanding memoization.

Aturan: Isi Tabel dari Kecil ke Besar #

Tabulation membangun solusi dengan urutan bottom-up: dari base case (sub-masalah terkecil) menuju masalah utama. Setiap entri tabel dihitung berdasarkan entri-entri yang sudah diisi sebelumnya.

Langkah umum:

1. Identifikasi state — apa yang menjadi indeks tabel?
2. Tentukan base case — entri terkecil yang sudah diketahui nilainya.
3. Tulis recurrence — rumus yang menghubungkan state besar dengan state lebih kecil.
4. Tentukan urutan iterasi — pastikan dependensi sudah dihitung sebelum digunakan.

Mekanisme: Iterasi Sistematis #

Pada tabulation, kita memilih urutan iterasi yang menjamin: setiap entri dp[i] hanya bergantung pada dp[j] dengan j < i (atau pola serupa). Untuk DP 1D sederhana, urutan ini biasanya dari kiri ke kanan. Untuk DP 2D, kita bisa mengisi per baris atau per kolom, asalkan dependensi terpenuhi.

Keuntungan utama tabulation:

• Tidak ada overhead pemanggilan fungsi.
• Tidak ada risiko stack overflow.
• Akses memori sekuensial — cache-friendly.
• Memungkinkan optimasi ruang (space optimization) dengan mudah.

Kode: Fibonacci Tabulation #

#include <iostream>
#include <vector>

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];
}

int main() {
    for (int n : {10, 20, 50, 80}) {
        std::cout << "fib_tabu(" << n << ") = " << fib_tabu(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

fib_tabu(10) = 55
fib_tabu(20) = 6765
fib_tabu(50) = 12586269025
fib_tabu(80) = 23416728348467685

1. Baris std::vector<long long> dp(n + 1);: alokasi tabel DP berukuran n+1. Indeks i menyimpan fib(i).
2. Baris dp[0] = 0; dp[1] = 1;: base case. Inilah titik awal iterasi.
3. Baris dp[i] = dp[i - 1] + dp[i - 2];: recurrence inti. Karena i-1 dan i-2 lebih kecil dari i, keduanya sudah dihitung sebelumnya.
4. Loop dari 2 hingga n: urutan iterasi menjamin dependensi terpenuhi. Tidak ada rekursi, tidak ada call stack.

Optimasi Ruang: 1D ke O(1) #

Banyak DP 1D hanya bergantung pada beberapa nilai sebelumnya. Kita bisa membuang array dan hanya menyimpan nilai yang dibutuhkan:

#include <iostream>

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() {
    for (int n : {10, 50, 90}) {
        std::cout << "fib_opt(" << n << ") = " << fib_opt(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

fib_opt(10) = 55
fib_opt(50) = 12586269025
fib_opt(90) = 2880067194370816120

1. Variabel prev2, prev1: hanya menyimpan dua suku terakhir. Habis memori: O(1).
2. Loop update: setiap iterasi menggeser jendela — prev2 jadi prev1 lama, prev1 jadi nilai baru.
3. Kompleksitas: O(n) waktu, O(1) ruang. Optimal untuk Fibonacci.

Tabulation 2D: Urutan Iterasi #

Pada DP 2D, urutan iterasi penting untuk menjamin dependensi terpenuhi. Contoh: LCS (Longest Common Subsequence) dengan recurrence:

dp[i][j] = dp[i-1][j-1] + 1                       jika s[i-1] == t[j-1]
         = max(dp[i-1][j], dp[i][j-1])            jika tidak

dp[i][j] bergantung pada dp[i-1][j-1], dp[i-1][j], dan dp[i][j-1] — semuanya berada di baris i-1 atau di kolom j-1 pada baris yang sama. Maka iterasi i dari 1 hingga n luar, j dari 1 hingga m dalam, menjamin dependensi terpenuhi:

Perbandingan Tabulation vs Memoization #

Kode: Tabulation untuk Coin Change #

Mari kita lihat tabulation pada masalah yang melibatkan iterasi bersarang:

#include <iostream>
#include <vector>
#include <climits>

int min_coins_tabu(const std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;  // base: 0 koin untuk nilai 0
    for (int i = 1; i <= amount; ++i) {
        for (int c : coins) {
            if (c <= i && dp[i - c] != INT_MAX) {
                dp[i] = std::min(dp[i], dp[i - c] + 1);
            }
        }
    }
    return dp[amount];
}

int main() {
    std::vector<int> coins = {1, 5, 10, 25};
    int amount = 63;
    std::cout << "Min koin untuk " << amount << " = "
              << min_coins_tabu(coins, amount) << '\n';
    return 0;
}

Output yang Dihasilkan:

Min koin untuk 63 = 6

1. Baris std::vector<int> dp(amount + 1, INT_MAX);: inisialisasi tabel. INT_MAX berarti “belum tercapai”.
2. Baris dp[0] = 0;: base case — butuh 0 koin untuk membentuk nilai 0.
3. Baris for (int i = 1; i <= amount; ++i): loop nilai dari kecil ke besar, menjamin dp[i-c] sudah dihitung.
4. Baris dp[i] = std::min(dp[i], dp[i - c] + 1);: coba ambil koin c, sisa i-c harus sudah minimum. Ambil minimum dari semua pilihan koin.

Ringkasan #

• Tabulation adalah DP bottom-up: isi tabel iteratif dari base case.
• Empat langkah: identifikasi state → tentukan base case → tulis recurrence → tentukan urutan.
• Keunggulan: tidak ada overhead rekursi, cache-friendly, mudah dioptimasi ruangnya.
• Optimasi ruang: bila dp[i] hanya butuh beberapa nilai sebelumnya, ganti array dengan variabel.
• Untuk state sparse, memoization sering unggul karena lazy evaluation.