Dynamic Programming Explained (for Beginners)

Dynamic programming (DP) solves a problem by breaking it into overlapping subproblems, solving each one only once, and storing the answers so they’re never recomputed. It’s the most feared interview topic, but underneath it’s a simple idea: it’s recursion plus a cache.

The fear comes from how DP is usually taught — abstractly. Build it up from a problem you already understand and it clicks. That’s what we’ll do here.

The two signals

A problem is a DP candidate when it has both:

1. Optimal substructure — the answer is built from answers to smaller versions of the same problem.
2. Overlapping subproblems — a plain recursion would solve the same subproblem again and again.

The second is the key. If subproblems don’t repeat, plain recursion or divide-and-conquer is enough; DP’s whole value is not recomputing.

From recursion to DP: Fibonacci

You’ve seen why naive recursive Fibonacci is disastrously slow — it recomputes the same values exponentially:

function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);   // recomputes fib(n-2) etc. → O(2ⁿ)
}

fib(5) computes fib(3) twice, fib(2) three times. Those repeats are the overlapping subproblems. DP eliminates them.

Approach 1 — Memoization (top-down)

Keep the natural recursion, but cache each result the first time you compute it:

function fib(n, memo = {}) {
  if (n < 2) return n;
  if (n in memo) return memo[n];          // already solved → reuse
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

Each value of n is computed once, so this is O(n) time. Memoization is top-down: you start from the big problem and recurse down, remembering as you go. It’s the easiest way to derive a DP solution — write the recursion, then add a cache.

Approach 2 — Tabulation (bottom-up)

Flip the direction: start from the smallest subproblems and build up a table iteratively, no recursion:

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

Same O(n), no recursion (so no stack-overflow risk), and you can often shrink the memory — here you only need the last two values, dropping space to O(1).

How to approach any DP problem

A repeatable recipe that demystifies most DP questions:

1. Define the state. What does a subproblem represent? (e.g. “the fewest coins to make amount i”.)
2. Write the recurrence. How does a state combine smaller states? (e.g. dp[i] = min(dp[i - coin] + 1) over coins.)
3. Set the base case. The smallest subproblem’s answer (e.g. dp[0] = 0).
4. Decide the order. Top-down memoization, or bottom-up table.

Get the state and recurrence right and the code is short — that’s why DP is “hard to design, easy to code.”

A worked example: climbing stairs

“How many ways to climb n stairs taking 1 or 2 steps at a time?” To reach step n, you came from step n-1 (one step) or n-2 (two steps), so:

ways(n) = ways(n - 1) + ways(n - 2)

That’s Fibonacci again — ways(n) is built from smaller ways, and they overlap. The same dp table solves it. Recognising that “ways to reach here = sum of ways to reach the places I could come from” is the DP insight.

Common DP problem families

• 1D sequences — climbing stairs, house robber, max subarray.
• Grids — unique paths, minimum path sum (move right/down).
• Knapsack — choose items under a constraint (coin change, subset sum).
• Strings — longest common subsequence, edit distance.

Most interview DP is a variation of one of these. Practising by family is how the patterns imprint.

Common mistakes

• Jumping to a table before writing the recursion — derive the recurrence first via memoization, then optimise.
• A wrong or fuzzy state definition — if you can’t state precisely what dp[i] means, the recurrence won’t be right.
• Missing or wrong base cases — the foundation the whole table builds on.
• Forcing DP where greedy or plain recursion suffices — DP only earns its keep when subproblems overlap.

Where this fits

Dynamic programming is the capstone of Phase 3 in the coding interview roadmap — the hardest pattern, built directly on recursion and measured by Big O (DP’s whole point is collapsing exponential recursion to polynomial time).

The recursion-to-memoization-to-tabulation progression and the major DP families are worked through with diagrams in our job-ready tier — JavaScript in Three Months, Python in Three Months, and Java in Three Months. For the harder DP that defines senior and staff interviews — 2D and interval DP, bitmask DP, and state-space optimisation — the for Staff Engineers tier goes deeper: JavaScript, Python, Java.

Write the recursion, spot the repeats, add a cache. That’s dynamic programming — far less scary than its reputation.