Dynamic Programming

If the same subproblem keeps coming back, solve it once, write the answer down, and read it the next time. That's the entire idea. "Dynamic programming" is a grand name for a deeply mundane trick — memoisation with taste — but the payoff is routinely turning exponential brute force into clean polynomial code.

The two preconditions

A problem is DP-shaped when two properties line up. Miss either one and DP is the wrong tool.

• Overlapping subproblems. The naive recursion keeps asking the same question with the same inputs. Classic example: computing Fibonacci with a raw recurrence asks for fib(5) many times while unrolling fib(10). If every recursive call has distinct arguments, you don't have overlap — and caching buys nothing.
• Optimal substructure. The optimal answer to the whole problem can be assembled from optimal answers to smaller instances of the same problem. Shortest paths have this; "find a path of exactly this colour sequence" often doesn't. When substructure is absent, local optima don't compose into a global optimum and DP produces wrong answers.

When both hold, you have a recurrence — a rule that expresses solve(x) in terms of solve(y) for some strictly-smaller y — and an opportunity to cache.

Memoisation vs tabulation

Two styles. Same answers, different feel.

Memoisation (top-down). Write the natural recursion, wrap it in a cache. First call with each input pays full cost; every repeat call is O(1).

const cache = new Map();
function climb(n) {
  if (n <= 1) return 1;
  if (cache.has(n)) return cache.get(n);
  const r = climb(n - 1) + climb(n - 2);
  cache.set(n, r);
  return r;
}

Tabulation (bottom-up). Solve the base cases first, fill a table forward, never recurse. Same asymptotic complexity, often faster in practice (no call-stack overhead, better cache locality) and easier to reason about iteratively.

function climb(n) {
  if (n <= 1) return 1;
  const dp = new Array(n + 1);
  dp[0] = dp[1] = 1;
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

Tabulation is what the playground on the next tab animates — left-to-right, cell by cell, because that's the shape your brain needs to hold while you debug.

Worked example — climbing stairs

You have n stairs. You can step 1 or 2 at a time. How many distinct paths to the top?

Let dp[i] = number of ways to reach step i. The last step you took was either a 1-step (from i-1) or a 2-step (from i-2), so:

dp[i] = dp[i-1] + dp[i-2], with dp[0] = dp[1] = 1.

Filling the table for n = 5:

i	dp[i]	from
0	1	base
1	1	base
2	2	1 + 1
3	3	2 + 1
4	5	3 + 2
5	8	5 + 3

That's Fibonacci in a trenchcoat. dp[n] = Fib(n+1).

Worked example — coin change

Given coins [1, 3, 4] and target 6, find the minimum number of coins that sum exactly to 6.

Let dp[i] = minimum coins to make amount i, or -1 if impossible. Base case dp[0] = 0 (empty purse). For i > 0:

dp[i] = 1 + min(dp[i - c]) over every coin c where c ≤ i and dp[i - c] ≠ -1.

Filling the table:

i	dp[i]	reasoning
0	0	base
1	1	1 + dp[0] = 1
2	2	1 + dp[1] = 2
3	1	1 + dp[0] via coin 3
4	1	1 + dp[0] via coin 4
5	2	1 + dp[4] via coin 1, or 1 + dp[2] via coin 3
6	2	1 + dp[3] via coin 3 — two 3-coins

The final answer dp[6] = 2. Notice how we always read dp[i - c] from the already-filled portion of the table; that's why left-to-right iteration is legal.

When DP wins over brute force

The brute-force climbing-stairs recursion revisits the same fib(k) exponentially many times — runtime O(φ^n), which blows up fast. DP turns it into O(n) time with O(n) memory (or O(1) memory if you only keep the last two values). Same answer, wildly different cost.

The pattern generalises: anywhere a recurrence has overlapping subproblems, DP typically pulls O(k^n) brute force down to O(n · states · work-per-state). For problems with n up to a few thousand and a polynomial number of states, that's the difference between sub-second and never finishes.

Signs a problem is DP-shaped

• You can write a recurrence — f(x) = combine(f(y_1), f(y_2), …) — where every y_i is strictly smaller than x.
• The same f(y) shows up in many branches of the recursion.
• You're choosing a min, max, count, or a boolean over alternatives (take-or-skip, left-or-right, use-coin-or-don't).
• The answer depends only on a small set of "state" parameters — index, remaining budget, last choice — not on the full path taken.

Real-world uses

• Route optimisation — shortest / cheapest paths under constraints (Bellman-Ford, Floyd-Warshall).
• Text diffing — the diff command, git diff, and every IDE "compare files" use Levenshtein / longest-common-subsequence DP.
• DNA sequence alignment — the Needleman-Wunsch and Smith-Waterman algorithms are DPs over strings.
• Knapsack packing — scheduling under memory / CPU budgets in resource-constrained systems, compilation register allocation, warehouse box-packing.
• Parsing — CYK parsing for context-free grammars is DP over substrings.

Common gotchas

• 1-D vs 2-D. Some problems need a table indexed by two parameters — dp[i][j] meaning "optimal answer over the first i items using budget j". The recurrence then reads from row i-1, not just column j-1. Knapsack and edit-distance are the canonical 2-D examples.
• Space optimisation. When your recurrence only reads from the previous row (or the last two values), you don't need the whole table — two rolling rows or a couple of scalars suffice. Write the full-table version first; optimise space only once it's correct.
• Off-by-one in base cases. dp[0] = 0 or dp[0] = 1? Depends on what the slot means. Write the meaning out in English — "dp[i] = the minimum number of coins to make i" — and the base case usually falls out.
• Unreachable vs zero. In coin change, "make amount 0" costs 0 coins, but "make amount 3 with only coin [2]" is unreachable. Conflating the two with the same sentinel breaks the min comparison — use -1 (or Infinity) distinctly.
• Order of fills. Left-to-right works only when each cell depends on strictly-smaller indices. If your recurrence reads dp[i + 1], you'd need right-to-left. Knapsack's "0/1 vs unbounded" distinction is exactly about fill order.

Playground

Pick climbing-stairs or coin-change, set the inputs, and press Play. The table fills left to right; the current cell flashes in var(--color-accent); its dependencies are outlined in var(--color-warning). Stepping through one frame at a time shows the recurrence doing its work.

Visualizer

The DP Animator runs climbing stairs for n = 10. Each frame highlights dp[i] being filled and the two cells it reads — dp[i-1] and dp[i-2]. Watch the values: they're Fibonacci, which is the entire reason climbing-stairs is the opening example in every DP lesson ever written.