Dynamic Programming Dasar

Kenapa ini penting

Dynamic programming (DP) punya reputasi menakutkan, padahal idenya sederhana: jangan menghitung hal yang sama dua kali. Kalau sebuah masalah bisa dipecah menjadi submasalah yang tumpang tindih (overlapping subproblems) dan jawaban terbaiknya tersusun dari jawaban terbaik submasalah (optimal substructure), kamu bisa menyimpan hasil submasalah dan memakainya ulang. Tech Interview Handbook menyebut "remove overlapping or repeated computation" sebagai salah satu teknik utama mengoptimasi waktu, dan DP adalah bentuk paling sistematisnya.

Analogi: kamu ditanya "berapa 1+1+1+1+1+1+1+1?" Kamu menghitung: 8. Lalu ditambah "+1" di ujung. Kamu tidak menghitung ulang dari awal; kamu langsung jawab 9 karena ingat jawaban sebelumnya. Itulah DP.

Untuk level junior-mid di perusahaan front-end/full-stack, DP yang ditanyakan biasanya DP satu dimensi atau grid sederhana. Kuasai polanya, jangan hafal soalnya.

Konsep inti

Dari rekursi ke DP: empat langkah

1. Tentukan state: apa arti dp[i]? Tulis dalam satu kalimat. Contoh: "dp[i] = jumlah cara mencapai anak tangga ke-i."
2. Tentukan transisi (recurrence): bagaimana dp[i] dihitung dari state sebelumnya? Contoh: dp[i] = dp[i-1] + dp[i-2].
3. Tentukan base case: dp[0], dp[1], dan seterusnya.
4. Tentukan urutan perhitungan dan jawaban akhir: dari kecil ke besar, jawabannya dp[n].

Memoization vs tabulation

Strategi interview yang aman: tulis brute force rekursif, tunjukkan pohon pemanggilannya bercabang dan berulang, tambahkan memo (sering cukup 3 baris), lalu kalau ditanya, ubah ke tabulation dan kecilkan ruangnya menjadi O(1) jika hanya butuh beberapa state terakhir.

Pola DP 1D yang paling sering

Contoh percakapan interview: dari brute force ke DP

Interviewer: "You can climb one or two steps at a time. How many distinct ways are there to reach step n?"

Candidate: "Let me try small cases first. For n equals 1 there's one way, for n equals 2 there are two ways: one plus one, or two. For n equals 3, my last move is either one step from step 2 or two steps from step 1, so it's ways(2) plus ways(1), which is 3. So ways(n) equals ways(n minus 1) plus ways(n minus 2), like Fibonacci."

Candidate: "A plain recursive solution would recompute the same subproblems many times, so it's exponential. If I cache each result, every subproblem is solved once: O(n) time and O(n) space. And since each step only depends on the previous two, I can keep just two variables and get O(1) space."

Interviewer: "What if you could take one, two, or three steps?"

Candidate: "Then the recurrence becomes the sum of the previous three values, with base cases for 0, 1, and 2. The structure stays the same."

Perhatikan bahwa kandidat menemukan recurrence dari contoh kecil, bukan dari hafalan. Itu cara paling aman di DP: hitung n = 1, 2, 3 secara manual, cari hubungannya, lalu tulis state dalam satu kalimat. Follow-up "bagaimana kalau aturannya berubah" sangat umum, dan kandidat yang paham state dan transisi bisa menjawabnya tanpa menulis ulang dari nol.

Contoh kode

// Fibonacci: dari rekursi polos ke DP
let calls = 0;
function fibNaive(n) { calls++; return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2); }   // O(2^n)
fibNaive(25); console.log('fibNaive(25) panggilan:', calls);
// → fibNaive(25) panggilan: 242785

function fibMemo(n, memo = new Map()) {          // top-down: O(n)
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const v = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, v); return v;
}
function fibTab(n) {                              // bottom-up: O(n) waktu, O(1) ruang
  let a = 0, b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}
console.log(fibMemo(25), fibTab(25), fibTab(50), fibMemo(70) === fibTab(70));
// → 75025 75025 12586269025 true

// Climbing Stairs: naik 1 atau 2 anak tangga
function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;                       // dp[1], dp[2]
  for (let i = 3; i <= n; i++) [prev2, prev1] = [prev1, prev1 + prev2];
  return prev1;
}
console.log([1, 2, 3, 4, 5, 10].map(climbStairs));
// → [ 1, 2, 3, 5, 8, 89 ]

// Coin Change: jumlah koin minimum (koin boleh dipakai berulang)
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;                                      // 0 koin untuk jumlah 0
  for (let a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
  return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(coinChange([1, 2, 5], 11), coinChange([2], 3), coinChange([1], 0), coinChange([1, 3, 4], 6));
// → 3 -1 0 2

// Kenapa greedy (ambil koin terbesar dulu) gagal di coin change
function coinGreedy(coins, amount) {
  let count = 0; for (const c of [...coins].sort((a, b) => b - a)) { count += Math.floor(amount / c); amount %= c; }
  return amount === 0 ? count : -1;
}
console.log('greedy [1,3,4] -> 6:', coinGreedy([1, 3, 4], 6), 'vs DP:', coinChange([1, 3, 4], 6));
// → greedy [1,3,4] -> 6: 3 vs DP: 2

// House Robber: tidak boleh merampok dua rumah bersebelahan
function rob(nums) {
  let skip = 0, take = 0;                          // terbaik s/d rumah sebelumnya: tidak diambil / diambil
  for (const money of nums) [skip, take] = [Math.max(skip, take), skip + money];
  return Math.max(skip, take);
}
console.log(rob([1, 2, 3, 1]), rob([2, 7, 9, 3, 1]), rob([]), rob([5]), rob([2, 1, 1, 2]));
// → 4 12 0 5 4

// Soal yang sama versi memoization (top-down)
function robMemo(nums) {
  const memo = new Map();
  const best = i => {
    if (i >= nums.length) return 0;
    if (memo.has(i)) return memo.get(i);
    const v = Math.max(best(i + 1), nums[i] + best(i + 2));   // lewati rumah i, atau ambil lalu lompat
    memo.set(i, v); return v;
  };
  return best(0);
}
console.log(robMemo([2, 7, 9, 3, 1]), robMemo([2, 1, 1, 2]));
// → 12 4

Angka 242.785 panggilan untuk fibNaive(25) adalah bukti nyata kenapa rekursi polos itu eksponensial; versi memo hanya menghitung 24 state berbeda. Test coinGreedy([1, 3, 4], 6) adalah contoh tandingan (counterexample) yang bagus untuk disebut ketika interviewer bertanya "Why not just take the biggest coin first?": greedy memilih 4+1+1 (3 koin), padahal 3+3 hanya 2 koin.

Satu catatan JavaScript: fibTab(50) = 12.586.269.025 masih aman karena di bawah Number.MAX_SAFE_INTEGER (2⁵³ − 1). Fibonacci di atas sekitar n = 78 melewati batas itu dan kehilangan presisi; pakai BigInt kalau soal meminta angka besar, atau tanyakan apakah jawabannya perlu modulo.

Kesalahan umum

1. Langsung menulis tabel tanpa mendefinisikan state. Kamu akan bingung sendiri. Cara benar: tulis komentar // dp[i] = ... sebelum kode.
2. Base case salah. Misalnya dp[0] = 1 di coin change versi minimum (harusnya 0). Cara benar: uji n = 0 dan n = 1 secara manual.
3. Memakai greedy tanpa bukti. Cara benar: cari counterexample kecil; kalau ada, pakai DP.
4. Memo dideklarasikan di luar fungsi dan tidak di-reset di antara test case, sehingga hasil test sebelumnya bocor. Cara benar: buat memo baru per pemanggilan utama.
5. Lupa menyebut optimasi ruang. Kalau transisi hanya butuh dua state terakhir, ruang bisa O(1). Interviewer sering menanyakan ini sebagai follow-up.

Latihan

1. Mudah, Min Cost Climbing Stairs: cost[i] adalah biaya menginjak anak tangga i; kamu boleh mulai dari indeks 0 atau 1 dan naik 1 atau 2 langkah. Berapa biaya minimum untuk melewati puncak?
2. Sedang, Unique Paths: robot di grid m × n hanya bisa ke kanan atau ke bawah. Berapa jalur dari kiri atas ke kanan bawah?
3. Menantang, Longest Increasing Subsequence (panjang saja), O(n²).

// 1. dp[i] = biaya minimum untuk berdiri di anak tangga i (tanpa membayar cost[i])
function minCostClimbingStairs(cost) {
  let a = 0, b = 0;                                 // dp[i-2], dp[i-1]
  for (let i = 2; i <= cost.length; i++) [a, b] = [b, Math.min(b + cost[i - 1], a + cost[i - 2])];
  return b;
}
console.log(minCostClimbingStairs([10, 15, 20]), minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]));
// → 15 6

// 2. dp[r][c] = dp[r-1][c] + dp[r][c-1]; cukup satu baris karena baris atas langsung ditimpa
function uniquePaths(m, n) {
  const row = new Array(n).fill(1);
  for (let r = 1; r < m; r++) for (let c = 1; c < n; c++) row[c] += row[c - 1];
  return row[n - 1];
}
console.log(uniquePaths(3, 7), uniquePaths(3, 2), uniquePaths(1, 1));
// → 28 3 1

// 3. dp[i] = panjang LIS yang BERAKHIR di indeks i
function lengthOfLIS(nums) {
  const dp = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++)
    for (let j = 0; j < i; j++) if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
  return nums.length ? Math.max(...dp) : 0;
}
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]), lengthOfLIS([0, 1, 0, 3, 2, 3]), lengthOfLIS([7, 7, 7]), lengthOfLIS([]));
// → 4 4 1 0

Ringkasan

• DP = submasalah tumpang tindih + optimal substructure; simpan hasil agar tidak dihitung ulang.
• Empat langkah: definisi state, transisi, base case, urutan perhitungan.
• Memoization (top-down) mudah diturunkan dari brute force; tabulation (bottom-up) bebas stack overflow dan mudah dihemat ruangnya.
• Climbing stairs, house robber, coin change, dan LIS adalah pola DP 1D inti.
• Cari counterexample sebelum memakai greedy; perhatikan batas Number.MAX_SAFE_INTEGER di JS.