S033 · Dynamic Programming — Memoisation & Tabulation

Module M03: Data Structures & Algorithms · Session 33 of 130 · Track: SW 🧩

What you'll be able to do after this session

• Explain Dynamic Programming to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S027 — Recursion — Call Stack, Base Case, Worked Examples

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Dynamic Programming in 5 Minutes — Reducible — visual explanation of overlapping subproblems using Fibonacci.
• 🎥 Deep dive (30–60 min) · MIT 6.006 Lecture 19: Dynamic Programming I — Erik Demaine's canonical 5-step DP recipe.
• 🎥 Hands-on demo (10–20 min) · NeetCode — Climbing Stairs (DP intro) — first DP problem coded three ways: recursion, memo, tabulation.
• 📖 Canonical article · Python functools.lru_cache docs — the decorator that turns any recursive function into a memoised one.
• 📖 Book chapter / tutorial · CP-Algorithms — Introduction to DP — clean derivations of knapsack, LIS, and edit distance.
• 📖 Engineering blog · Google Research — Neural Machine Translation & Beam Search — beam search is essentially bounded DP; production sequence models rely on it.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Break the problem down, cache the answer.

You're planning a road trip from Delhi to Chennai and asking Google Maps for the fastest route. Internally it doesn't try every possible sequence of cities — that would be 26! combinations. Instead it notes, "the fastest way from Bangalore to Chennai is X hours" and reuses that answer no matter which route into Bangalore you took. That reuse — "if I've already solved this subproblem, don't solve it again" — is dynamic programming in one sentence.

DP works when two conditions hold: (1) overlapping subproblems — you keep needing the answer to the same smaller question, and (2) optimal substructure — the best answer for the big problem is built from best answers of smaller problems. Fibonacci is the textbook example: fib(50) naively takes 2⁵⁰ calls because it keeps recomputing fib(48), fib(47), … With DP it's 50 calls total, one per unique subproblem.

The two flavours are just implementation choices. Memoisation (top-down) = write the natural recursion, add a cache; runs subproblems only when needed. Tabulation (bottom-up) = fill an array from the base case up; no recursion, no stack overflow.

The forever gotcha: if you can't clearly state "what is f(n) in one sentence?" you don't have a DP formulation yet — you have wishful thinking. Define the state first, transitions second, base case last.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

The Fibonacci call tree — see why naive recursion is exponential:

fib(3) computed twice, fib(2) three times. At fib(50) the duplication is astronomical. Memoisation collapses this tree into a single line: solve each fib(k) once, cache the answer.

The 5-step DP recipe (Erik Demaine, MIT 6.006):

Worked example — 0/1 Knapsack. Items with (weight, value): [(2,3), (3,4), (4,5), (5,6)], capacity W=5.

State: dp[i][w] = max value using first i items with capacity w.

Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi) if wi <= w.

Best value at capacity 5 = 7 (items 1 & 2: weights 2+3=5, values 3+4=7). Each cell used two earlier cells → O(nW) total work.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

Save as dp_lab.py and run with python3 dp_lab.py:

from functools import lru_cache
import time
 
# 1. Naive recursion — exponential
def fib_naive(n):
    if n < 2: return n
    return fib_naive(n-1) + fib_naive(n-2)
 
# 2. Memoisation (top-down) — one line change
@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2: return n
    return fib_memo(n-1) + fib_memo(n-2)
 
# 3. Tabulation (bottom-up) — no recursion, O(1) extra space
def fib_tab(n):
    if n < 2: return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b
 
def bench(fn, n, label):
    t = time.perf_counter()
    r = fn(n)
    print(f"{label:12s} fib({n}) = {r} in {(time.perf_counter()-t)*1000:.2f} ms")
 
# 0/1 Knapsack — tabulation
def knapsack(items, W):
    n = len(items)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = items[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]
            if wi <= w:
                dp[i][w] = max(dp[i][w], dp[i-1][w - wi] + vi)
    return dp[n][W]
 
# Edit distance (Levenshtein) — memoisation
def edit_distance(a, b):
    @lru_cache(maxsize=None)
    def f(i, j):
        if i == 0: return j
        if j == 0: return i
        if a[i-1] == b[j-1]:
            return f(i-1, j-1)
        return 1 + min(f(i-1, j), f(i, j-1), f(i-1, j-1))
    return f(len(a), len(b))
 
if __name__ == "__main__":
    bench(fib_memo, 35, "memo");   fib_memo.cache_clear()
    bench(fib_tab,  35, "tab")
    bench(fib_naive, 30, "naive")   # 35 would take ~30s
    print("knapsack:", knapsack([(2,3),(3,4),(4,5),(5,6)], 5))       # 7
    print("edit_distance('kitten','sitting'):", edit_distance("kitten","sitting"))  # 3

Checklist — observe when you run:

1. fib_naive(30) takes ~200ms; fib_memo(35) and fib_tab(35) are sub-millisecond. Cache size vs raw compute.
2. lru_cache hits and misses are tracked — call fib_memo.cache_info() after a run to see.
3. knapsack returns 7; trace the DP table (Layer b) with pen and paper to verify.
4. edit_distance("kitten","sitting") = 3 (k→s, e→i, insert g). This is the algorithm behind diff, spell-check, DNA alignment.
5. Delete the @lru_cache decorator from edit_distance — timing on strings of length 20 blows up.

Try this modification: convert knapsack from O(nW) space to O(W) space using a 1-D rolling array. Iterate w from W down to wi — why does the direction matter?

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

DP hides inside almost every "smart" algorithm you use daily:

• git diff, VS Code diff view, GitHub PR view — all built on the Myers diff algorithm, which is DP on edit distance.
• Spell check & autocomplete — Levenshtein distance, weighted DP with keyboard-locality costs.
• Bioinformatics — Needleman-Wunsch and Smith-Waterman DNA alignment are literal knapsack cousins; they run on petabytes at Broad Institute and Illumina.
• Speech recognition & translation — Viterbi decoding (HMM), CTC decoding, beam search. Google's transformer NMT paper is DP wrapped around neural scoring.
• Query optimisers — Postgres's join-order planner uses DP (System-R algorithm) to enumerate up to 12-way joins; beyond that it falls back to a genetic algorithm because the DP state space explodes.

War story — the interview whiteboard trap. Junior engineers try to write DP top-down with a global dict, forget the base case, and produce an off-by-one that's nearly impossible to debug on a whiteboard. The senior-engineer move: write the recurrence in English first, on the corner of the board. "f(i,j) = min cost to transform first i chars of A into first j chars of B." Then the code writes itself.

Common production bugs:

• State explosion. DP with a 3-D state on n=1000 blows up to 10⁹ cells → 8 GB. Reduce state dimensions before you optimise the constant factor. LeetCode "House Robber III" has 2D solutions that reduce to 1D once you see the trick.
• Memoisation with mutable keys. Using a list as an lru_cache argument throws TypeError: unhashable. Convert to tuple first.
• Python recursion limit. Deep DP (n=10000) hits RecursionError: maximum recursion depth exceeded in Python. Either sys.setrecursionlimit(20000) or convert to bottom-up. Java/C++ have no such issue with stack size within reason.
• Floating-point DP. Summing probabilities in Viterbi drifts; switch to log-space (sum → max of sums) and you avoid underflow.

The pattern-recognition tell: whenever a problem says "find the minimum / maximum / count number of ways to do X" and X has clear "choices at each step," reach for DP before recursion + for loop.

(e) Quiz + exercise · 10 min

1. State the two properties a problem must have for DP to apply.
2. Explain the difference between memoisation and tabulation in one sentence each. When would you pick one over the other?
3. Naive fib(50) takes billions of calls; memoised fib(50) takes 50. Explain why in terms of the call tree.
4. Write the DP recurrence for "climbing stairs where you can hop 1, 2, or 3 steps at a time."
5. What Python decorator turns a plain recursive function into a memoised one, and what's its main limitation?
6. Stretch (connects to S027 Recursion): Every memoised DP is a recursion with a cache. Show how to convert the edit_distance memoised solution above into a bottom-up tabulation. Which of the two would you ship to production and why?

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Dynamic Programming? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S034): Greedy & Backtracking — When to Use Each
• Previous (S032): Binary Search — the Pattern Behind 100 Problems
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.