🧩 Data Structures & Algorithms · Chapter 16

Dynamic programming, from recursion

Dynamic programming isn't a new algorithm. It's your slow recursive solution, plus a notebook so it never solves the same subproblem twice.

Study this lesson free in the app →

The basics

Dynamic programming (DP) solves a problem by breaking it into smaller subproblems, solving each once, storing the answer, and reusing it whenever that subproblem comes up again.

The problem it solves: many natural recursive solutions recompute the same thing over and over. Naive fib(40) makes over 300 million calls, yet there are only 41 different questions being asked. Store each answer the first time and the work drops from exponential to linear.

The mental model: someone writes 1+1+1+1+1+1+1+1 on a board and asks for the total. You count: 8. They add "+1" at the end. You answer 9 instantly — you didn't recount, you remembered 8. That's DP.

The recipe: (1) write the recursion, (2) spot repeated calls, (3) cache them (memoisation, top-down) or fill a table from the smallest case up (tabulation, bottom-up), (4) keep only the rows you still need.

Cost: time = number of distinct subproblems × work per subproblem. Space = size of the table (or memo), often reducible.

Explained

Naive fib(40): 331 million function calls, several seconds or more in Python.

Same code with one line added — @cache — 79 calls, under a millisecond.

That one line is the whole idea of dynamic programming. The rest is learning to spot when it applies and how to write it without recursion.

The tiled path

A garden path is 5 tiles long. A child crosses it taking either 1 tile or 2 tiles per step. How many different ways can she cross?

She stands before the last tile. She arrived either from tile 4 (a 1-step) or from tile 3 (a 2-step). So:

ways(5) = ways(4) + ways(3)

And ways(4) = ways(3) + ways(2)… Notice ways(3) is needed twice already. Work up from the start instead: ways(1) = 1, ways(2) = 2, then 3, 5, 8. Five additions, each reusing the two answers before it. No one recounts a path they've already counted.

From recursion to DP in four moves

1. Define the state — what identifies a subproblem? For stairs: n, the number of tiles left.
2. Write the recurrence + base cases — ways(n) = ways(n-1) + ways(n-2), ways(1) = 1, ways(2) = 2.
3. Remove repeats

- Top-down (memoisation): keep the recursion, cache results by state. - Bottom-up (tabulation): fill dp[1], dp[2], …, dp[n] in a loop, so every value you need is already computed.

1. Shrink the space — if dp[i] only reads dp[i-1] and dp[i-2], keep two variables.

Check the two ingredients first: overlapping subproblems (otherwise caching does nothing — merge sort never repeats a call) and optimal substructure (the best answer is made of best sub-answers).

The waste: naive fib(6)

25 calls to compute fib(6) = 8. fib(4) is computed twice, fib(3) three times, fib(2) five times. The repeats are the overlapping subproblems — the tree grows by about ×1.6 for each +1 to n.

The fix: memoised fib(6)

Each fib(k) is computed once and written down; later requests are lookups. The counter shows 11 calls, but 4 of them are instant memo hits — only 7 (fib(0) to fib(6)) do real work — O(n) time, O(n) space for the memo and the stack. Same answer, a fraction of the work.

Fibonacci, four ways

from functools import cache

def fib_naive(n):        # O(2ⁿ) time, O(n) stack
    return n if n <= 1 else fib_naive(n - 1) + fib_naive(n - 2)

@cache
def fib_memo(n):         # top-down: O(n) time, O(n) memo + stack
    return n if n <= 1 else fib_memo(n - 1) + fib_memo(n - 2)

def fib_table(n):        # bottom-up: O(n) time, O(n) table, no recursion
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def fib_roll(n):         # O(n) time, O(1) space
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

fib_roll(10)             # 55

Same recurrence each time. Only the bookkeeping changes — and with it, the time and space.

Counting the cost of a DP

Time = number of states × work per state. Space = what you keep.

problem              state        time            space (best)
──────────────────────────────────────────────────────────────
fib / stairs         n            O(n)            O(1) rolling
coin change          amount       O(amount × k)   O(amount)
grid paths m × n     (r, c)       O(m × n)        O(n) one row
0/1 knapsack         (item, cap)  O(n × W)        O(W) one row
longest common       (i, j)       O(m × n)        O(min(m, n))
  subsequence

(k = number of coin types, W = capacity.)

Watch the hidden size: knapsack with W = 10⁹ is O(n × 10⁹) — 'polynomial' in the number, but far too slow. DP pays when the number of distinct states is small, even if the number of paths through them is astronomically large: a 20 × 20 grid has over 35 billion right/down paths, but only 400 states.

Gotchas

• Caching without overlap — @cache on merge sort or a tree walk just wastes memory; no state repeats.
• Greedy instead of DP — 'always take the biggest coin' fails for {1, 3, 4} → 6. Prove greedy or use DP.
• Wrong state — if the answer depends on something not in the state (e.g. remaining capacity), cached answers get reused where they don't apply.
• Deep memoised recursion in Python — fib_memo(5000) from cold raises RecursionError. Tabulate, or warm the cache bottom-up.
• Mutable arguments — @cache needs hashable arguments; pass tuples, not lists.
• Wrong loop order in tabulation — every dp[x] you read must already be filled; iterate from base cases outward.
• Off-by-one base cases — dp[0] = 0 for coins (zero coins make zero) but ways(0) = 1 for counting (one way to do nothing).

Words to know

In two minutes

• DP = recursion + reuse: solve each distinct subproblem once and store it.
• It applies when subproblems overlap and the best answer is built from best sub-answers (optimal substructure).
• Recipe: define the state, write the recurrence and base cases, then memoise (top-down) or tabulate (bottom-up).
• Time = distinct states × work per state. Fibonacci: n states × O(1) = O(n), down from O(2ⁿ).
• Space = the table. Often only the last row or last two values are needed: fib drops to O(1) space.
• Memoisation is easiest to write but recurses (Python's ~1,000-frame limit); tabulation is a loop with no depth limit.
• Classic shapes: climbing stairs / Fibonacci, coin change O(amount × coins), grid paths O(rows × cols), knapsack O(n × capacity).

Test yourself

There are 8 questions, 4 puzzles and 6 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.