Dynamic Programming

Dynamic programming (DP) sounds scary but is one idea: do not solve the same subproblem twice. When a recursive solution keeps recomputing identical calls, you cache the results — and an exponential algorithm collapses to polynomial.

DP applies when a problem has two properties: overlapping subproblems (the same smaller problems recur) and optimal substructure (the best answer is built from best answers to subproblems). Fibonacci is the canonical teaching example.

The problem: exponential recomputation

Naive fib(n) = fib(n-1) + fib(n-2) re-derives the same values over and over. The call tree branches exponentially — fib(5) already computes fib(2) three times.

Fix 1 — Memoization (top-down)

Keep the natural recursion but store each result the first time you compute it. Every subproblem is then solved once: O(2ⁿ) → O(n).

function fib(n, memo = new Map()) {
  if (n < 2) return n
  if (memo.has(n)) return memo.get(n)      // reuse
  const result = fib(n - 1, memo) + fib(n - 2, memo)
  memo.set(n, result)                      // remember
  return result
}

Fix 2 — Tabulation (bottom-up)

Flip it around: fill a table from the smallest subproblems up to the answer, so every value you need is already computed. No recursion, no stack — often the interviewer’s preferred form.

function fib(n) {
  if (n < 2) return n
  let a = 0, b = 1
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b]
  return b
}

How to spot and solve a DP problem

1. Signals: "count the ways", "min/max cost", "can you reach…", "longest/shortest subsequence".
2. Define the state — what parameters uniquely describe a subproblem (e.g. dp[i] = best answer using the first i items).
3. Write the recurrence — how a state is built from smaller states.
4. Set the base cases, then compute top-down (memo) or bottom-up (table).
5. Optionally reduce space by keeping only the rows/columns you still need.