Memoization & Dynamic Programming — Algoritma

Dynamic Programming (DP) menyelesaikan masalah kompleks dengan memecahnya jadi sub-masalah yang overlap, dan menyimpan hasilnya agar tidak dihitung ulang…

Memoization artinya mencatat hasil function yang sudah dihitung, supaya kalau ditanya lagi tinggal ambil dari catatan. Ini salah satu cara dynamic programming (DP): memecah masalah jadi sub-masalah kecil yang muncul berulang, lalu menghitung tiap sub-masalah sekali saja. Mirip mencatat jumlah halaman buku tebal sesudah menghitungnya, supaya gak perlu menghitung ulang waktu ditanya lagi.

🧪 Tebakan cepat: fib(5) versi rekursif biasa memanggil dirinya berapa kali: 5, 9, atau 15? Tebak dulu, jawabannya ada di bagian "Masalahnya: hitungan yang diulang".

Masalahnya: hitungan yang diulang

Deret Fibonacci: 0, 1, 1, 2, 3, 5, 8, ... Tiap angka adalah jumlah dua angka sebelumnya, jadi fib(5) = fib(4) + fib(3). Tapi fib(4) sendiri butuh fib(3) lagi, dan seterusnya. Ini berapa kali tiap panggilan muncul saat menghitung fib(5):

Panggilan Berapa kali dihitung
fib(5) 1
fib(4) 1
fib(3) 2
fib(2) 3
fib(1) 5
fib(0) 3

Total 15 panggilan, padahal yang beda cuma 6. Itu jawaban tebakannya.

let calls = 0;

function fib(n) {
  calls++;
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // dua cabang, dihitung ulang terus
}

console.log(fib(5)); // 5
console.log(calls); // 15

Jumlah panggilannya hampir dua kali lipat tiap n naik 1. fib(40) butuh sekitar 331 juta panggilan, cukup untuk bikin browser macet kira-kira satu detik.

Memo: catat, lalu pakai lagi

const memo = {};

function fib(n) {
  if (n <= 1) return n;
  if (n in memo) return memo[n]; // sudah pernah dihitung: ambil dari catatan
  memo[n] = fib(n - 1) + fib(n - 2); // hitung sekali, lalu catat
  return memo[n];
}

console.log(fib(40)); // 102334155, langsung keluar

Dengan memo, tiap fib(k) dari 0 sampai 40 cuma dihitung sekali: 41 hitungan, dari tadinya 331 juta panggilan. Kerjanya jadi O(n): n dua kali lipat, kerjanya kira-kira dua kali lipat. Lab lesson ini memakai Map untuk catatannya (memo.has(n), memo.get(n), memo.set(n, hasil)); cara kerjanya sama persis.

Catatan juga bisa dibawa sebagai parameter dengan nilai bawaan: function fibMemo(n, memo = {}). Nilai bawaan {} cuma dipakai di panggilan pertama. Supaya semua panggilan memakai catatan yang sama, kirim terus memo-nya: fibMemo(n - 1, memo).

Tabel: dari kecil ke besar

Memoization disebut juga DP top-down: mulai dari masalah besar, turun lewat rekursi. Cara lainnya bottom-up atau tabulation: isi tabel dari yang paling kecil pakai loop biasa.

function fibTabel(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

console.log(fibTabel(10)); // 55

dp[i] menyimpan fib(i), dan tiap isi dihitung dari dua isi sebelumnya yang sudah ada. Tanpa rekursi, jadi gak ada risiko stack overflow untuk n besar. DP cuma berguna kalau sub-masalahnya berulang, seperti fib(3) tadi. Kalau tiap sub-masalah cuma muncul sekali, catatan cuma menghabiskan memori.

⚠️ Jebakan yang sering ketemu

TL;DR: Memoization mencatat hasil yang sudah dihitung di object memo (atau Map): cek memo dulu, kalau belum ada hitung lalu simpan di memo[n]. Fibonacci rekursif biasa menghitung hal yang sama berulang kali (fib(40) sekitar 331 juta panggilan); dengan memo tiap fib(k) dihitung sekali, jadi O(n). Kalau memo jadi parameter, kirim terus ke tiap panggilan. Tabulation (bottom-up) mengisi tabel dari kecil ke besar pakai loop. DP berguna kalau sub-masalahnya berulang.

Yang akan kamu pelajari