Dynamic Programming

Dynamic programming (DP) solves problems by breaking them into overlapping subproblems, computing each subproblem once, and storing the result. It transforms exponential-time brute-force solutions into polynomial-time ones.

When to Use DP

A problem is a DP candidate when it has two properties: optimal substructure (the optimal solution is built from optimal solutions to smaller inputs) and overlapping subproblems (the same smaller inputs are solved repeatedly).

Top-Down: Memoization

Write the natural recursive solution, then cache each result the first time it is computed. Simple to implement from the recursive formulation.

// Fibonacci — O(2^n) naive, O(n) with memo
function fib(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

// Coin change — minimum coins to make amount
function coinChange(coins, amount, memo = {}) {
  if (amount in memo) return memo[amount];
  if (amount === 0) return 0;
  if (amount < 0) return Infinity;
  let min = Infinity;
  for (const coin of coins) {
    min = Math.min(min, 1 + coinChange(coins, amount - coin, memo));
  }
  memo[amount] = min;
  return min;
}

Bottom-Up: Tabulation

Build a table of subproblem solutions starting from the smallest cases and work up to the answer. Avoids recursion overhead and is often faster in practice.

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

// Coin change bottom-up — classic DP table
function coinChangeTab(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

0/1 Knapsack

Given items with weights and values and a capacity limit, maximise total value without exceeding capacity. Each item can only be used once.

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i-1][w]; // skip item i
      if (weights[i-1] <= w) {
        dp[i][w] = Math.max(dp[i][w], values[i-1] + dp[i-1][w - weights[i-1]]);
      }
    }
  }
  return dp[n][capacity];
}

Longest Common Subsequence (LCS)

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

lcs('ABCBDAB', 'BDCABA'); // 4

Memoization vs Tabulation

• Memoization: easier to write from the recursive formulation; only computes needed subproblems
• Tabulation: no recursion overhead; better cache performance; always computes all subproblems
• Both have the same asymptotic complexity — pick whichever is clearer for the problem