What Dynamic Programming Actually Is: Overlapping Subproblems and Optimal Substructure

Hook #

Dynamic programming has the worst name in computer science. It's not particularly dynamic; it's not programming in the modern sense. Richard Bellman (who invented it in 1953) picked the name partly to obscure what he was actually doing — recursive optimisation — from a defence-budget reviewer who hated the word "research." The legacy: every engineer's first encounter with DP is confused. This lesson un-confuses it. DP is a paradigm for problems where greedy fails and brute-force recursion is exponentially slow. The trick is remembering subproblem answers. Once you see the trick, every DP problem looks the same; the only variation is what the subproblem is.

What you'll be able to do by the end of this lesson #

• State the two preconditions for DP: overlapping subproblems and optimal substructure.
• Recognise when a problem has each property (and when it doesn't — those problems need greedy, D&C, or something else).
• Distinguish memoisation (top-down — cache recursive results) from tabulation (bottom-up — fill a table from base cases up).
• Convert a recursive brute-force algorithm into a memoised version by adding ~3 lines of code.
• Articulate why DP is "smart brute force" — it explores the same search space as exponential recursion but pays for each unique state only once.

A quick try before we start #

Suppose I ask you to compute the 50th Fibonacci number using this recursive function:

rubydef fib(n)
  return n if n < 2
  fib(n - 1) + fib(n - 2)
end

fib(50) takes minutes on a modern laptop. fib(60) takes hours. fib(100) won't finish in your lifetime.

What's the algorithm doing wrong? Specifically — not "it's slow" but what work is it duplicating? Predict your answer before reading on.

If you can draw the recursion tree for fib(5) on paper, you'll see the problem immediately.

The core idea, from first principles #

The two preconditions #

A problem is DP-shaped iff it has both:

1. Overlapping subproblems. The naive recursive solution computes the same subproblem many times. In fib(5), the recursion calls fib(3) twice. In fib(50), it calls fib(3) billions of times. The recursion tree has the same sub-tree appearing in many places.

2. Optimal substructure. The optimal solution to the problem can be constructed from optimal solutions to subproblems. Fibonacci: fib(n) = fib(n-1) + fib(n-2). Shortest path from A to B through C: shortest A→C + shortest C→B (if C is on the optimal path). Knapsack: optimal value with capacity W = max(skip item / take item) of optimal solutions to smaller subproblems.

These are both required. Greedy algorithms need optimal substructure but not overlapping subproblems (greedy choices commit at each step; no need to revisit). Divide-and-conquer needs optimal substructure but not overlapping subproblems (subproblems are independent). DP is the paradigm for problems with both.

Why this gives DP its power #

Without DP, recursive code on a problem with overlapping subproblems takes exponential time. With DP, the same problem takes polynomial time — because each unique subproblem is computed once and remembered. The speedup is enormous: O(2ⁿ⁾ becomes O(n).

The mental model: DP is brute-force recursion plus a cache. The cache turns repeated work into a single lookup. Everything else is bookkeeping.

Let's see it for Fibonacci.

Naive recursive (the disaster) #

rubydef fib(n)
  return n if n < 2
  fib(n - 1) + fib(n - 2)
end

The recursion tree for fib(5):

text                fib(5)
              /        \
          fib(4)       fib(3)
         /     \       /    \
      fib(3) fib(2) fib(2) fib(1)
      /   \   /  \   /  \
    fib(2) f(1) f(1) f(0) f(1) f(0)
    /  \
   f(1) f(0)

fib(3) appears twice. fib(2) appears three times. fib(1) appears five times. fib(0) appears three times.

For fib(n), the recursion tree has O(2^n) leaves. Exponential. The work is the same fib(k) for various k, computed redundantly.

Memoised recursive (top-down DP) #

Add a cache. Before computing, check the cache; if the answer is there, return it. If not, compute and store.

rubydef fib(n, memo = {})
  return n if n < 2
  return memo[n] if memo.key?(n)
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
end

Three lines added: memo = {} (initialise cache), return memo[n] if memo.key?(n) (check cache), memo[n] = ... (store before return).

Now: fib(50) runs in microseconds. fib(100) runs in microseconds. fib(1000) runs in microseconds (Ruby's bignums handle the big numbers).

What changed? Each unique fib(k) is computed once. After fib(3) is computed, it goes in the cache. The next time fib(3) is requested, it's returned in O(1) from the cache. Total work: O(n) to compute all unique values; O(n) to retrieve them. O(n) total.

The recursion tree, after memoisation, is a DAG — directed acyclic graph. Each node appears once; multiple parents point to the same node. This is the structural fact behind DP: the recursion tree, when redundant computations are collapsed, becomes a DAG of size O(n) — not a tree of size O(2ⁿ⁾.

Tabulated (bottom-up DP) #

Same algorithm, different ordering. Instead of recursing top-down (request fib(50); recurse down to base cases; build back up), we go bottom-up: start at the base cases and fill a table up to the desired value.

rubydef fib(n)
  return n if n < 2
  table = [0, 1]
  (2..n).each { |i| table[i] = table[i - 1] + table[i - 2] }
  table[n]
end

Three things to notice:

• No recursion. Just a loop.
• No cache. The table array is the cache; the loop fills it in order.
• Same time complexity (O(n)), same answer. The two approaches are equivalent in cost; they differ in ordering.

This is tabulation (bottom-up DP). The trade-offs vs. memoisation:

Both are valid DP. Pick whichever fits your problem and constraints better. Memoisation is usually easier to write first; tabulation is what production code often becomes after optimisation.

A worked example: coin change #

Problem: given coin denominations [1, 3, 4] and a target amount, what's the minimum number of coins needed to make the target?

This is the canonical "greedy fails, DP wins" problem from Course 3.3 lesson 3.

Naive recursive:

rubydef min_coins(coins, amount)
  return 0 if amount == 0
  return Float::INFINITY if amount < 0
  best = Float::INFINITY
  coins.each do |c|
    sub = min_coins(coins, amount - c)
    best = sub + 1 if sub + 1 < best
  end
  best
end

Exponential. Calling min_coins([1, 3, 4], 20) explores billions of paths.

Memoised:

rubydef min_coins(coins, amount, memo = {})
  return 0 if amount == 0
  return Float::INFINITY if amount < 0
  return memo[amount] if memo.key?(amount)

  best = Float::INFINITY
  coins.each do |c|
    sub = min_coins(coins, amount - c, memo)
    best = sub + 1 if sub + 1 < best
  end
  memo[amount] = best
end

Three lines added: cache check, cache store. Polynomial. min_coins([1, 3, 4], 1000) runs in milliseconds.

The state of the DP is the remaining amount. There are amount possible states; each is computed once; each computation iterates coins. Total: O(amount × |coins|).

Tabulated:

rubydef min_coins(coins, amount)
  table = Array.new(amount + 1, Float::INFINITY)
  table[0] = 0
  (1..amount).each do |a|
    coins.each do |c|
      next if a - c < 0
      table[a] = table[a - c] + 1 if table[a - c] + 1 < table[a]
    end
  end
  table[amount]
end

Same algorithm; bottom-up. Same O(amount × |coins|).

The state is the same; the order of evaluation differs. Notice how similar the structure is — DP problems share a shape: define the state; relate states via the recurrence; fill the table.

Why this works the way it does #

The deep reason: DP collapses exponential search into polynomial computation by exploiting *structure. Specifically, the *overlapping-subproblems property guarantees that exponential search visits the same sub-states repeatedly; optimal substructure guarantees that the optimal answer is some combination of optimal answers to those sub-states. The combination — overlap + optimality — is what makes the cache work.

Without optimal substructure, you can't combine subproblem answers into a global answer; the cache would still work but the algorithm would be wrong (greedy choice property doesn't hold either; the problem needs a fundamentally different approach).

Without overlapping subproblems, the cache never hits — every subproblem is unique. The algorithm becomes plain recursion (or D&C if subproblems are smaller versions). The cache adds overhead with no payoff.

The historical reason: Bellman's 1953 work on multistage decision processes (operations research). He noticed that many decision problems — when to act, what action to take given a current state — had the property that the optimal current decision depended only on the optimal future decisions from the resulting state. This is exactly optimal substructure. Combine with the realisation that the same states recur across decision sequences (overlapping subproblems), and you have DP. Bellman's Principle of Optimality is the foundational statement; CLRS Chapter 15.3 has the formal version.

The reason DP is so common in interviews and competitive programming: it's the paradigm where naive code is obviously wrong (exponential time) and the fix is non-obvious but mechanical. The mental shift — from "code is the algorithm" to "the recurrence is the algorithm; the code is one way to compute it" — is the single biggest jump in algorithmic maturity. Once you have it, half the optimisation tricks in computing become familiar.

Explain it back to me #

A junior engineer writes a recursive solution to a problem. It works on small inputs (n=10) but hangs on larger ones (n=30). They want to optimise.

In your own words, what's the first question to ask them — not about their algorithm, but about the problem? Use the words "overlapping subproblems" and "optimal substructure."

And a second: a teammate looks at the memoised Fibonacci above and says "that's just caching." Untangle this. Is "DP" the same as "caching"? What's the difference between "I cached this function's result" and "I solved this problem with DP"?

A small exercise #

Three short tasks:

1. Identify whether each problem has overlapping subproblems and/or optimal substructure: a. Find the minimum coin change for an arbitrary target. b. Sort an array in ascending order. c. Find the shortest path between two cities in a road network. d. Determine whether a number is prime. e. Find the longest increasing subsequence of an array.

2. Memoise this recursive function in 3 added lines: ruby def grid_paths(m, n) return 1 if m == 1 || n == 1 grid_paths(m - 1, n) + grid_paths(m, n - 1) end (This counts paths through an m × n grid moving only right or down.)

3. Trace a small DP table by hand. Use the tabulated min_coins([1, 3, 4], _) and fill in the table for amounts 0 through 10. (Hint: table[0] = 0; table[1] = 1; table[3] = 1; ...)

Where this connects #

Backward: Course 3.3 lesson 1 (paradigm lens) introduced DP as one of the four paradigms; lesson 2 (greedy) showed where greedy fails; lesson 3 (greedy correctness) gave you the tools to prove greedy wrong on coin change. This lesson is the follow-on: when greedy fails because the locally optimal choice isn't part of the globally optimal solution, DP picks up by exploring all options and caching the answers. Course 2.2 lesson 1 (recursive mind-shift) gave you structural recursion; DP is structural recursion plus memoisation.

Forward: Lesson 2 (1D DP patterns) gives you a vocabulary of 1D subproblem patterns. Lesson 3 (the DP recipe) is the procedure for converting any recursive brute force into a DP solution. Lesson 4 (2D DP classics) covers the heavyweight pattern (LCS, edit distance, matrix chain). Lesson 5 (knapsack menu) covers the patterns you'll see most in production and interviews. Course 4.2 (Graph Algorithms) returns to DP with Floyd-Warshall (DP on graphs). Course 11.x (AI) returns to DP with Markov decision processes and reinforcement learning — both built on Bellman's original framing.

The zc-dp-pattern-catalog project for this course is your hands-on opportunity to recognise DP patterns across many problems. Build it after lesson 5; by then you'll have the recognition skills to populate the catalog correctly.

Carry forward one mental habit: when you write a recursive function that looks slow, ask "are subproblems overlapping?" If yes, memoise. The fix is three lines. The speedup is exponential.