Dynamic Programming: From Memoization to Tabulation With 10 Classic Problems Solved

// DP signals in problem statement:
// "minimum/maximum number of..."
// "how many ways to..."
// "is it possible to..."
// "longest/shortest subsequence/path..."
// Any problem where brute force explores exponential possibilities

// Template: ask these questions
// 1. Can I break this into smaller subproblems?
// 2. Do subproblems repeat? (overlapping)
// 3. Does optimal subproblem → optimal full solution? (optimal substructure)
// If yes to all: DP likely applies

// Brute force: O(2^n)
// DP memoization (top-down): O(n)
function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibMemo(n-1, memo) + fibMemo(n-2, memo);
  memo.set(n, result);
  return result;
}

// DP tabulation (bottom-up): O(n) time, O(1) space
function fibDP(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];
  return curr;
}

// Given coins [1,5,10,25] and amount 41, min coins to make change?
// State: dp[i] = minimum coins to make amount i
// Transition: dp[i] = min(dp[i - coin] + 1) for each coin <= i

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // Base case: 0 coins to make amount 0

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] + 1 < dp[i]) {
        dp[i] = dp[i - coin] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
coinChange([1, 5, 10, 25], 41); // 4: [25, 10, 5, 1]
// Time: O(amount × coins), Space: O(amount)

// LCS("ABCBDAB", "BDCABA") = 4 ("BCBA")
// State: dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]
function lcs(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i-1] === s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
      else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[m][n];
}
// Time: O(m×n), Space: O(m×n)
// Used in: diff tools, DNA sequence alignment

// Items with weights and values, bag capacity W, max value?
// Each item: take it (0/1) or leave it
function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({length: n+1}, () => new Array(W+1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      // Don't take item i:
      dp[i][w] = dp[i-1][w];
      // Take item i (if it fits):
      if (weights[i-1] <= w) {
        dp[i][w] = Math.max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
      }
    }
  }
  return dp[n][W];
}
// Time: O(n×W), Space: O(n×W) — can optimize to O(W)