Dynamic Programming, Visualized

The whole idea, in one breath.

Dynamic programming is what you do when a recursion repeats itself. Instead of solving the same subproblem ten thousand times, you solve it once, write the answer down, and look it up next time it appears.

That's the entire trick. The hard part is just two things: noticing that subproblems overlap, and figuring out the recurrence that ties them together. Everything else — top-down memoization, bottom-up tables, optimizing space — is implementation detail.

01 / The setup

Overlapping subproblems

The same smaller question gets asked over and over. Without memory, you re-derive its answer every time.

02 / The hinge

Optimal substructure

The answer to a problem is built from the answers to smaller versions of itself. A clean recurrence exists.

03 / The move

Remember answers

Compute each subproblem once. Cache it (memoize) or fill a table bottom-up (tabulate). Done.

The two examples below are the cleanest illustrations of these ideas. The first shows you the waste that DP eliminates. The second shows you the table that DP fills.

Example I.

Fibonacci numbers.

F(n) = F(n−1) + F(n−2), with F(0) = 0 and F(1) = 1. The most innocent recursion in computer science — and a complete disaster if you actually run it that way.

Below is the call tree for F(5). Same color = same value. Notice how often the colors repeat. Each repeat is a subproblem you computed from scratch when you didn't have to.

Fig. 1 — Recursion tree, F(5)

Total calls: 15

F(3) is computed twice. F(2) three times. F(1), five times. The naive call count grows like F(n+1) itself — exponentially. With memoization, every value is computed exactly once, and the redundant subtrees collapse into cache lookups.

15 function calls for naive F(5). With memoization, this drops to 9 — a ~40% saving on a tiny tree. The gap explodes as n grows.

The fix is a table.

Once you see the duplicates, the patch is obvious: write each answer down the first time. Even cleaner — build the table from the bottom up, so you never need to recurse at all.

The bottom-up DP table. Each cell is filled once, reading two cells to its left. Linear time, constant space if you keep only the last two values.

function fib(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

The exponential tree collapsed into a linear walk. That's what DP buys you on this problem — and the savings only get more dramatic as n grows. F(50) goes from ~25 billion calls down to 51.

Example II.

Counting paths in a grid.

Stand in the top-left of a grid. You may step right or down only. How many distinct paths reach the bottom-right corner?

The recurrence almost writes itself. To reach any cell, you must have arrived from the cell directly above it or directly to its left. So the number of paths to a cell is the sum of paths to those two predecessors.

paths(i,j) = paths(i−1, j) + paths(i, j−1)

Edge cells — the top row and left column — have exactly one path to them, straight along the edge. Those are your base cases. Now fill the table, row by row.

Fig. 2 — Paths in a 4×5 grid

Step 0 / 20

Answer: —

Watch the gold cells (sources) feed the teal cell (current). Each new value is the sum of the two it points back to. The bottom-right cell holds the final count: every distinct path through the grid, tallied exactly once.

function uniquePaths(rows, cols) {
  const dp = Array.from({length: rows}, () => Array(cols).fill(1));
  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[rows - 1][cols - 1];
}

This is tabulation in its purest form. We never recurse — we just walk the table in an order that guarantees every dependency is already computed. Fill, look back, sum, advance.