Memoization

Memoization adalah teknik DP top-down di mana kita menulis fungsi rekursif seperti biasa, tetapi setiap hasil sub-masalah disimpan ke cache sebelum dikembalikan. Saat sub-masalah yang sama dipanggil lagi, cache langsung memberikan jawaban tanpa rekursi ulang. Pendekatan ini terasa natural karena struktur kode tetap mengikuti definisi rekursif masalah. Pada Chapter ini kita akan membedah cara kerja memoization, kapan menggunakan array versus hash map, serta kelebihan dan kekurangannya dibanding tabulation.

Aturan: Cache Sebelum Return #

Prinsip memoization sangat sederhana: sebelum sebuah fungsi rekursif mengembalikan nilai, nilai tersebut ditulis ke struktur data cache (array, vector, atau unordered_map). Saat fungsi dipanggil lagi dengan argumen yang sama, fungsi membaca dari cache dan langsung kembali.

Struktur umum fungsi memoized:

1. Cek cache — bila sudah ada, langsung kembalikan.
2. Base case — kondisi berhenti rekursi.
3. Rekursi — panggil diri sendiri untuk sub-masalah.
4. Tulis cache — simpan hasil sebelum return.

Mekanisme: Lazy Evaluation #

Memoization adalah bentuk lazy evaluation. Sub-masalah hanya dievaluasi saat benar-benar dibutuhkan oleh pemanggil. Bila beberapa sub-masalah tidak pernah dipanggil, cache untuk sub-masalah tersebut tidak diisi.

Keuntungan utama:

• Hanya menghitung sub-masalah yang relevan dengan masukan.
• Struktur kode mengikuti definisi rekursif masalah, mudah ditulis dan dibaca.
• Recurrence yang melibatkan banyak state kompleks lebih mudah diekspresikan.

Kode: Fibonacci dengan Memoization #

#include <iostream>
#include <vector>

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

int main() {
    int n = 50;
    std::vector<long long> memo(n + 1, -1);
    std::cout << "fib(" << n << ") = " << fib_memo(n, memo) << '\n';

    // Tunjukkan cache yang terisi
    std::cout << "Isi memo (n=0..10): ";
    for (int i = 0; i <= 10; ++i) std::cout << memo[i] << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

fib(50) = 12586269025
Isi memo (n=0..10): -1 -1 1 2 3 5 8 13 21 34 55

1. Baris std::vector<long long> memo(n + 1, -1);: alokasi cache berukuran n+1, diisi sentinel -1 yang berarti “belum dihitung”. Gunakan long long karena Fibonacci cepat overflow.
2. Baris if (memo[n] != -1) return memo[n];: cek cache pertama kali. Bila cache terisi, kembalikan langsung — tidak ada rekursi tambahan.
3. Baris memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);: hitung sekali, simpan ke cache. Inilah inti memoization.
4. Hasil fib(50) = 12586269025: selesai dalam milidetik. Tanpa memo, fib(50) butuh miliaran panggilan.
5. memo[0] dan memo[1] tetap -1: dua indeks pertama ditangani oleh base case (if (n <= 0) return 0; dan if (n == 1) return 1;) sebelum mencapai baris penulisan cache, sehingga tidak pernah disimpan.

Cache Berbentuk Array vs Hash Map #

Untuk state berdimensi kecil dengan rentang nilai yang rapat (misal fib(0..n)), array vector adalah pilihan terbaik: akses O(1), konstanta kecil, cache-friendly.

Untuk state multi-dimensi atau rentang nilai jarang, gunakan std::map atau std::unordered_map:

Kode: Memoization dengan unordered_map #

Contoh: masalah coin change (jumlah minimum koin untuk membentuk nilai amount). State-nya satu dimensi, tetapi mari kita tunjukkan pendekatan map untuk perbandingan:

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

int min_coins(int amount, const std::vector<int>& coins,
              std::unordered_map<int, int>& memo) {
    if (amount < 0) return INT_MAX;
    if (amount == 0) return 0;
    auto it = memo.find(amount);
    if (it != memo.end()) return it->second;

    int best = INT_MAX;
    for (int c : coins) {
        int sub = min_coins(amount - c, coins, memo);
        if (sub != INT_MAX) best = std::min(best, sub + 1);
    }
    memo[amount] = best;
    return best;
}

int main() {
    std::vector<int> coins = {1, 5, 10, 25};
    std::unordered_map<int, int> memo;
    int amount = 63;
    int result = min_coins(amount, coins, memo);
    std::cout << "Min koin untuk " << amount << " = " << result << '\n';
    std::cout << "Jumlah state di cache = " << memo.size() << '\n';
    return 0;
}

Output yang Dihasilkan:

Min koin untuk 63 = 6
Jumlah state di cache = 63

1. Baris auto it = memo.find(amount);: lookup di hash map. Bila ditemukan, kembalikan langsung.
2. Baris for (int c : coins): coba setiap koin — ini adalah bagian “transisi” dalam DP.
3. Baris if (sub != INT_MAX) best = std::min(best, sub + 1);: bila sub-masalah solvable, tambahkan 1 (koin saat ini) dan ambil minimum. INT_MAX digunakan sebagai penanda “tidak tercapai”.
4. Jumlah state = 63: lazy evaluation membuat kita hanya mengisi state yang relevan dengan amount = 63. Tidak ada state untuk nilai yang lebih besar.

Kelebihan dan Kekurangan Memoization #

Kelebihan:

• Struktur kode natural mengikuti definisi rekursif.
• Lazy evaluation — hanya menghitung sub-masalah yang dibutuhkan.
• Mudah diimplementasikan untuk recurrence kompleks.

Kekurangan:

• Overhead pemanggilan fungsi (call stack).
• Risiko stack overflow untuk n besar (default stack ~8 MB di Linux, cukup untuk ribuan frame).
• Konstanta faktor lebih besar dibanding iterasi murni.

Kapan Memoization Menang #

Memoization unggul ketika:

• Hanya sebagian kecil sub-masalah yang benar-benar dibutuhkan (sparse state space).
• Recurrence sangat kompleks dan tabulation membutuhkan banyak base case.
• Inline quick fix — kita tinggal menambahkan array memo ke fungsi rekursif yang sudah ada.

Untuk masalah yang membutuhkan semua sub-masalah diselesaikan (misal LCS, edit distance), tabulation seringkali lebih cepat karena tidak ada overhead rekursi.

Ringkasan #

• Memoization adalah DP top-down: tulis rekursi natural, simpan hasil ke cache.
• Empat langkah: cek cache → base case → rekursi → tulis cache.
• Gunakan vector untuk state kecil rapat, unordered_map untuk state sparse.
• Lazy evaluation menghemat perhitungan bila banyak sub-masalah tidak dibutuhkan.
• Kekurangan: overhead rekursi dan risiko stack overflow untuk n besar.