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

Memoization (top-down): tambahkan cache ke rekursi.

// Fibonacci tanpa memo — O(2ⁿ)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// Fibonacci dengan memo — O(n) 🚀
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

fib(40);     // 😱 SANGAT LAMBAT (> 1 detik)
fibMemo(40); // ⚡ INSTAN

Tabulation (bottom-up): bangun tabel dari kecil ke besar.

// Fibonacci bottom-up — O(n) time, O(n) space
function fibTab(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

// Optimasi space — O(1)
function fibOpt(n) {
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

Contoh klasik DP: Climbing Stairs

// Berapa cara naik n tangga jika bisa 1 atau 2 langkah?
function climbStairs(n) {
  if (n <= 2) return n;
  let prev = 1, curr = 2;
  for (let i = 3; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

climbStairs(5); // 8 cara

Kapan pakai DP?

• Sub-masalah overlap (dihitung berkali-kali)
• Masalah punya optimal substructure (solusi optimal dibangun dari sub-solusi optimal)

🎭 Analogi sehari-hari: Hitung manual jumlah halaman buku tebal. Pertama kali kamu hitung: 1 jam. Tutup buku, tanya temen "berapa halaman?" — kamu hitung lagi? Atau catet dulu hasilnya? Catet = memoization. Selalu catet hasil yang sudah dihitung supaya gak ngulang.

💡 Memoization vs Tabulation:

• Memoization (top-down): rekursi + cache. Mulai dari masalah besar, cache hasil sub-problem yang ditemui
• Tabulation (bottom-up): loop iteratif. Mulai dari sub-problem terkecil, build up ke besar

Tabulation lebih cepat (no recursion overhead) tapi memoization lebih intuitif untuk pemula.

⚠️ Jebakan umum:

• DP without overlap = pakai DP padahal divide & conquer cukup. Cek dulu apakah ada subproblem yang dihitung berkali-kali
• State space terlalu besar = OOM. DP butuh memori (cache). Cek dulu space requirement
• Salah definisi state = solusi salah. Definisikan dp[i] = ? dengan sangat jelas
• Lupa initial conditions = base case salah → seluruh DP salah

🎯 Pola "ini DP problem":

• "Optimal count / min / max dari kumpulan pilihan" → DP
• "Berapa cara untuk..." → DP counting
• "Bisa atau gak..." → DP boolean
• Klasik: knapsack, longest common subsequence, edit distance, coin change, fibonacci, partition

🧪 Tebakan cepat: fib(50) naive ~1.5 milyar calls. With memo? 51 unique computations. Speedup: ~30 juta kali. DP optimization shines paling extreme di overlapping subproblem.

TL;DR: DP = pecah masalah, cache hasil sub-problem yang overlap. Memoization (top-down) atau Tabulation (bottom-up). Wajib: overlap subproblems + optimal substructure. Tools utama untuk problem optimasi exponential.