Dynamic Programming — Memoisation & Tabulation

Dynamic programming: state before storage

Learning objective: derive a sufficient state, transition, base case and valid evaluation order; implement memoization or tabulation; then count the actual states, transitions and retained storage.

The examples use nonnegative integer Fibonacci/stair indices, nonnegative integer amounts/capacities, positive integer coin denominations and weights, and equal-length knapsack weight/value lists. Empty choices are allowed. The zero-step staircase has one empty path. Caching does not imply optimization or polynomial time: a correct state can still have exponentially many possible values. Costs below count elementary operations unless bit growth is explicitly discussed; no timing is a platform-independent promise.

Why this session exists

Dynamic programming reuses solutions to well-defined states instead of recomputing equivalent histories. A compact state space can turn exponential recursion into polynomial work; subset states may remain exponential. Sequence alignment and finite-state decoding are important applications, while arbitrary language-model beam search is approximate search, not automatically exact DP. Learn the modelling recipe rather than a promise to solve every problem in five minutes.

You will be able to

• Recognise reusable states and overlap; for optimization, justify optimal substructure under a sufficient state.

• Apply the 4-step recipe: define state, write the transition, name the base case, choose the fill order.

• Convert a plain recursion to a memoised version by adding @lru_cache(maxsize=None) and to a tabulated version by deriving a dependency-respecting fill order.

• Explain the space-vs-time trade of memo vs tabulation, and when to prefer each.

• Compute Fibonacci, climbing stairs, coin change, LIS (O(n²) and O(n log n)), and edit distance without reference.

Prerequisites

• S027 — Recursion — Call Stack, Base Case — top-down DP builds on recursion and reusable state.
• S023 — Arrays & Lists — tabulation lives in a 1-D or 2-D array.
• S032 — Binary Search — the O(n log n) LIS uses it.

Optional archived resources

The original videos are retained as optional links; identity, playback and duration were not reverified. Use the primary source notes for accepted claims.

• What is Dynamic Programming? — original attribution: Reducible; compare repeated call labels.
• Lecture 19 · Dynamic Programming I — original attribution: MIT OpenCourseWare; derive subproblems and evaluation order. The official MIT page is linked in source notes.
• 5 Simple Steps for Solving Dynamic Programming Problems — original attribution: Reducible; practice stating the coin-change recurrence.

Pre-read · choose a resource and derive one recurrence

Further reading: functools.lru_cache — Python docs

Archived optional link: Edit Distance / Levenshtein Distance — retained, not used as governing evidence; the recurrence is fully derived below.

Archived optional link: Google Research link from the original lesson — no claim that it establishes Myers deployment at Google; use the original Myers paper below.

(a) Intuition · 5 min

The forgetful vs the note-taking mathematician

A forgetful mathematician expands fib(30) into fib(29) + fib(28) and recomputes equal arguments along many branches. For the displayed naive recurrence, the exact call count is 2*F(n+1)-1: at n=30 this is 2,692,537 calls and 1,346,268 additions, not a billion. Caching arguments 0 through n reduces the work to O(n) state evaluations; at n=30 there are 29 non-base additions.

Reusable states and overlapping subproblems

• Sufficient state: histories can share an answer only if the state determines all remaining legal choices, costs and transitions. In an optimization problem, prove that optimal solutions compose from optimal subproblem solutions under that state. Fibonacci is a counting/recurrence example, not an optimization problem requiring a maximum or minimum.
• Overlap: repeated states motivate caching. Merge sort absolutely uses smaller sorted subanswers, but its usual disjoint subarrays do not yield the repeated positional states that Fibonacci does. Lack of overlap limits the benefit of a cache, not correctness of memoizing a pure function.
• Affordable state space: n Fibonacci indices fit a linear table; (visited_subset, endpoint) can have O(n·2ⁿ) states despite abundant overlap. Greedy needs its own proof; it is not automatically valid whenever overlap is absent.

The 4-step recipe — write this on paper for every DP

State — what parameters uniquely identify a subproblem? (For fib: one integer n.) Transition — how does the answer at state s compose from smaller states? (For fib: f(n) = f(n-1) + f(n-2).) Base case — the smallest states you know outright. (For fib: f(0)=0, f(1)=1.) Order — the order to fill the table so every state's dependencies are ready. (For fib: 0, 1, 2, …, n.)

Get those four right and the code writes itself. Skip any one and you're guessing.

Timeline — recurrences, alignment and bounded search

Bellman's dynamic-programming work established a reusable way to describe staged optimization through value functions. The important distinction is the optimality principle under a sufficient state, not the original lesson's unsourced naming anecdote. Edit distance gives a concrete two-prefix recurrence; Myers' 1986 paper derives an O(ND) shortest insert/delete edit-script algorithm, where N is total input length and D the minimum script length. This is not the same edit-cost model as Levenshtein substitution-at-cost-one.

Modern finite-state decoding can merge histories that share a sufficient state. Beam search instead retains only a bounded set of hypotheses and may prune the globally best continuation. The historical progression does not justify the former assertion that every LLM token is produced by exact DP or beam search.

(b) From repeated calls to reusable states · 15 min

The four-step recipe begins with a state, not a cache. Fibonacci makes that distinction visible: calls reached by different paths can still ask exactly the same question.

The naive Fibonacci call tree — an explosion

Compare the labels rather than the positions of the nodes. Every occurrence of fib(3) requests the same result, and its descendants repeat the same work; those repeated requests are what memoisation can share.

The red labels mark repeated state requests in this partial call tree (not every branch is expanded). For the exact naive recurrence, fib(50) makes 2*F(51)-1 = 40,730,022,147 calls, Θ(φ⁵⁰), not approximately 2⁵⁰. An initially empty unbounded cache evaluates just 51 distinct states; recursive cache-hit requests still occur.

Caching changes how often a state is evaluated without changing its recurrence. Once those states are identified, the next choice is whether to discover them recursively or fill them in dependency order.

Two dialects of the same idea

Name: Top-down · memoisation

Tagline: Recursion + cache

• Write the natural recursion

• Decorate with @lru_cache(maxsize=None)

• Computes only the states you actually need

• Uses stack space (risk of RecursionError)

• Often natural to derive from a recurrence; debugging difficulty depends on the state

• Prefer when subproblem space is sparse

Name: Bottom-up · tabulation

Tagline: Iterative fill of a table

• Allocate a 1-D or 2-D array

• Loop from base cases to the answer

• A dense table visits its allocated range; a designed sparse bottom-up order can visit only selected states

• No recursion — no stack limit

• Enables ‘rolling window’ space optimisation

• Prefer dense spaces, explicit evaluation order or a proven rolling-storage reduction; the achievable storage depends on dependencies

The 4-step recipe applied to coin_change(coins, amount)

Problem: given coins [1, 3, 4], find the minimum number of coins summing to amount = 6. Answer: 2 (3 + 3), not 3 (4 + 1 + 1).

1. State

Desc: dp[i] = minimum coins to make amount i. One integer parameter → 1-D table.

2. Transition

Desc: Try every positive coin as the last one used: dp[i] = 1 + min((dp[i-c] for c in coins if c <= i), default=float("inf")). An empty set of feasible predecessors stays unreachable; the default avoids calling min on an empty generator.

3. Base case

Desc: dp[0] = 0 (zero coins make amount 0). All others start at ∞.

4. Order

Desc: Fill dp[1], dp[2], …, dp[amount] in ascending order — each state depends only on smaller ones.

Fibonacci: three implementations side by side

Coin change showed how to define a table; returning to Fibonacci lets us separate the implementation choices from that modelling step. Read each arrow as a change in what work or storage is retained, not a change in the answer being computed.

For Fibonacci the rolling version uses a constant number of integer variables. Python integers grow with n, so this is not constant bit-space: F(n) has Θ(n) bits and the loop performs O(n²) bit work with linear-cost integer addition. Other DP dependencies may require whole rows, subsets or decisions; not every DP admits rolling O(1) storage.

The last arrow works because each Fibonacci value needs only the preceding two. Before applying that storage reduction to another problem, inspect its dependencies: the shape of the state space tells you what must remain available.

The state-space taxonomy — what kind of DP is this?

Common state-space shapes — not an exhaustive classification

Name: 1-D over position

Desc: Fibonacci, climbing stairs, house robber, coin change. State = one integer.

Name: Subset plus any future-relevant boundary

Desc: Travelling salesman typically uses (visited_subset, last_city), not the subset alone, with O(n·2ⁿ) states and up to n transitions each. Assignment can infer the next worker from subset size. A 20-item threshold is not a universal memory/time guarantee.

Name: 2-D over two sequences

Desc: Edit distance and longest common subsequence use two prefix lengths. Matrix-chain multiplication instead uses interval endpoints within one chain and considers split points, giving a different transition cost.

Name: 2-D over position + resource

Desc: Knapsack (item index × remaining capacity), stock problems (day × holding-state).

Name: DP on trees

Desc: Diameter and subtree summaries combine child results in postorder. On a proper tree each node may be visited once, so an extra memo dictionary is unnecessary; this is often called tree DP even without repeated calls.

Name: DP on DAGs

Desc: Longest path, topological-order relax. Same as 1-D but the order is a topological sort.

A state-space label is a starting point, not a correctness argument. The examples that follow test whether the chosen state contains enough information and whether earlier results can safely be reused or overwritten.

Myth: "Dynamic programming means caching. If I slap @lru_cache on my recursive function, I'm doing DP."

Caching a pure function with a sufficient key preserves its answers whether or not it solves an optimization problem. A wrong recurrence or incomplete state gives wrong answers; lack of overlap affects the benefit of caching, not its validity.

Why: Because memoisation genuinely does convert the textbook example — Fibonacci — from exponential to linear, and that transformation is so dramatic it looks like the whole technique. The reusable Fibonacci state is just the index. Harder problems need a proof that the proposed key retains future-relevant information, plus a count of states and transitions; a decorator cannot supply those arguments.

Test the cache mechanism separately from optimization. The original merge_sort_len returns n and does not recursively sort anything; calling it twice with the same n does create a cache hit. A node-only state is insufficient for a longest simple path in a cyclic graph because legality depends on already visited vertices. A (visited_subset, endpoint) state can reuse histories, but has exponentially many possible states. In a DAG, longest paths need only a vertex state and topological evaluation.

from functools import lru_cache
 
@lru_cache(None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
 
@lru_cache(None)
def merge_sort_len(n):
    # A pure identity function, NOT a merge sort or a claim about slice overlap.
    return n
 
assert fib(20) == 6765
merge_sort_len(8)
merge_sort_len(8)
assert merge_sort_len.cache_info().hits == 1

A mutable argument such as a list fails hashability with TypeError; that is not a slow cache miss. A default identity-hashable instance is a valid self key, but changes to its fields are absent from that key and can produce stale answers. Freeze the relevant input, include an immutable version/state in the key, or explicitly invalidate the cache.

Question: Why can the 0/1 knapsack DP table be collapsed from a 2-D array to a single 1-D array — and why must that 1-D loop then run backwards? Reversing a loop to fix correctness looks like black magic. It is forced.

Premise: The recurrence is dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt] + val) — row i depends only on row i−1.

Because: each item is either taken or not, and both branches consult the state before this item was considered

Premise: Since only the previous row is ever read, rows 0..i−2 are dead and need not be stored.

Because: nothing in the recurrence reaches back more than one row

Premise: So you can overwrite a single array in place — but only if, when computing cell w, the cells you read still hold previous-row values.

Because: the recurrence's right-hand side is defined in terms of row i−1, not row i

Premise: The read is at index w - wt, which is strictly less than w. So the cells you read are to the left of the cell you write.

Because: item weights are positive

Premise: Iterating w from high to low therefore writes only to cells whose left-hand dependencies have not yet been touched this round; iterating low to high would overwrite them first.

Because: you must consume a value before you clobber it

Conclusion: Therefore the backward loop is not a trick — it is the minimal condition for the in-place array to still represent row i−1 where it is read. Memory drops from O(n·W) to O(W) with zero change to the answer. And note what this predicts: run the loop forwards and you get a bug for the stated 0/1 contract, though it computes a different, correct unbounded variant under the same positive-weight assumptions. A forward loop lets a cell see this-row values, meaning an item can be reused, which is exactly the unbounded knapsack. One loop direction distinguishes "each item once" from "items unlimited". Go verify that; it is the cleanest example anywhere that loop order encodes semantics.

Name: Fill the table, then read one cell

Picture: Stop thinking recursively. Think: there is a table. Each cell is a fully answered question about a smaller version of the problem. You fill it in an order that guarantees every dependency is already filled, and the answer to the real problem is sitting in one corner. Designing a DP needs all four decisions: state, transition, base cases and evaluation order. A topological order is appropriate for an acyclic dependency graph; cyclic value equations need additional convergence or relaxation reasoning.

• Define the state as an English sentence first: "dp[i][j] = the best achievable using the first i items with capacity j". If you cannot write that sentence, you do not have a DP yet.

• Complexity sums all transition costs over evaluated states; a uniform upper bound is states × transitions per state × cost per transition. Include hashing, slicing and growing-integer operations where applicable, plus initialization and output work.

• Top-down visits states reached by the recurrence and may be natural to derive. Bottom-up avoids recursive frames and often has smaller overhead; benchmark equivalent workloads before claiming it is always faster. Either approach needs sufficient state and a termination argument.

• A visited set is a compressed history: different orders can reach the same set and endpoint, so subset DP has overlap. Keeping the entire ordered path often destroys that sharing. Count the states before choosing exact DP, backtracking or an approximation.

Trigger: Fire this model the moment you see: "maximum / minimum / count the number of ways" over a sequence of choices · edit distance or sequence alignment · a problem whose brute force is exponential but whose inputs are small integers · Spark's cost-based join reordering (that is DP over subsets) · Viterbi decoding · any optimisation where a choice at step i only interacts with a bounded summary of steps 1..i−1.

Decision: The exact DP is O(n·W) and W is huge — a knapsack over budget in paise, or a state space with a continuous dimension. Exact DP, greedy, or approximation?

Name: Exact DP

Gain: exact when the recurrence and state are correct. Reconstructing choices additionally requires stored predecessors/decisions, a retained table or recomputation; a rolling optimum value alone does not contain the witness.

Cost: total work sums transition costs over states. Capacity-indexed knapsack is O(n·W) in numeric W, which can be exponential in W's encoded bit length. Thus this pseudo-polynomial algorithm does not establish polynomial time for the binary-encoded problem; it is not itself a proof of NP-hardness.

Pick: the measured state/transition count and representation fit the CPU and memory budget. A million Python objects and a million packed integers have different memory costs; there is no universal capacity threshold.

Name: Greedy

Gain: a proven greedy rule can avoid a large state table; running time and storage depend on sorting, queues and the chosen problem, not a universal O(n log n)/constant-memory rule.

Cost: exactness needs a valid problem-specific argument such as exchange or a cut property; matroids are one sufficient framework, not a necessary condition for every greedy algorithm. Some nonexact greedy algorithms have proven approximation ratios, while unproved heuristics need not.

Pick: you can actually prove the exchange argument (interval scheduling, Huffman, MST) — never on the grounds that it "seems reasonable"

Name: Scale/round the state, or use an FPTAS

Gain: for suitable problems, such as nonnegative-value 0/1 knapsack, an FPTAS scales profits and uses a value-indexed DP with a proven multiplicative loss bound and time polynomial in input size and 1/ε. It is not arbitrary rounding of the capacity-indexed table.

Cost: you must be able to state and defend the error bound, and rounding can interact badly with hard constraints (a budget you must not exceed)

Pick: use approximation only when the problem admits the required guarantee and the application accepts it.

For nonnegative-profit 0/1 knapsack, first discard individually overweight items. If the largest remaining profit V is zero, the optimum is zero. Otherwise, for N remaining items and 0 < ε < 1, set K=εV/N and rounded profit floor(value/K). An exact DP minimizing weight for each rounded-profit sum retains capacity feasibility. Rounding loses less than K per selected item, hence less than NK=εV≤ε·OPT; maximizing rounded profit gives at least (1−ε)·OPT in original value. Each rounded profit is at most N/ε, so the total rounded-profit range is O(N²/ε). This derives the simple FPTAS idea; no approximation implementation or numerical-rounding behavior is claimed tested here.

Verdict: first remove state dimensions that can be derived without changing future choices. Then count states and transitions, not just table axes. Dependencies constrain parallelism but do not forbid it: edit-distance anti-diagonals have independent cells once earlier diagonals are ready. Other DPs are irregular or communication-heavy. Choose exact DP, proven greedy or a bounded approximation according to the problem and budget, not a blanket “DP is single-machine” rule.

(c) Hands-on · 25 min

Save as dp_lab.py, run with python3 dp_lab.py.

"""dp_lab.py — six classic DP problems in one file."""
from __future__ import annotations
import bisect
from functools import lru_cache
from typing import List
 
# ---------- 1. Fibonacci — three implementations ----------
def fib_naive(n: int) -> int:
    """Exponential call count; use small nonnegative n in this teaching lab."""
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
 
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    """Top-down: O(n) additions, O(n) cached integers and recursive frames."""
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)
 
def fib_tab(n: int) -> int:
    """Bottom-up: O(n) additions and two growing integer variables."""
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
 
# ---------- 2. Climbing stairs — the ‘hello world’ of DP ----------
def climb_stairs(n: int) -> int:
    """Ways to climb n stairs taking 1 or 2 steps at a time. = fib(n+1)."""
    if n == 0:
        return 1
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
 
# ---------- 3. Coin change — minimum coins ----------
def coin_change(coins: List[int], amount: int) -> int:
    """Fewest coins summing to `amount`, or -1 if impossible."""
    INF = float("inf")
    dp = [0] + [INF] * amount            # dp[0] = 0; rest start unreachable
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i and dp[i - c] + 1 < dp[i]:
                dp[i] = dp[i - c] + 1
    return dp[amount] if dp[amount] != INF else -1
 
# ---------- 4. Longest Increasing Subsequence — O(n²) and O(n log n) ----------
def lis_quadratic(nums: List[int]) -> int:
    """dp[i] = LIS ending at i. O(n²) but easy to remember."""
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
 
def lis_nlogn(nums: List[int]) -> int:
    """Patience-sort DP with binary search — the interview flex."""
    tails: List[int] = []                # tails[k] = smallest possible tail of an LIS of length k+1
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)              # extend
        else:
            tails[i] = x                 # tighten
    return len(tails)
 
# ---------- 5. Edit (Levenshtein) distance — 2-D DP ----------
def edit_distance(a: str, b: str) -> int:
    """Minimum single-character insert/delete/replace to turn `a` into `b`."""
    m, n = len(a), len(b)
    # dp[i][j] = distance between a[:i] and b[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                     # delete all of a[:i]
    for j in range(n + 1):
        dp[0][j] = j                     # insert all of b[:j]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],        # delete a[i-1]
                    dp[i][j - 1],        # insert b[j-1]
                    dp[i - 1][j - 1],    # replace
                )
    return dp[m][n]
 
# ---------- 6. 0/1 Knapsack — the OR classic ----------
def knapsack(weights: List[int], values: List[int], capacity: int) -> int:
    """Max value packable into capacity; each item usable at most once."""
    n = len(weights)
    dp = [0] * (capacity + 1)            # rolling 1-D over items
    for i in range(n):
        w, v = weights[i], values[i]
        for c in range(capacity, w - 1, -1):   # iterate BACKWARDS so we don't reuse item i
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]
 
# ---------- Demo ----------
if __name__ == "__main__":
    print("fib_memo(50)         =", fib_memo(50))
    print("fib_tab(100)         =", fib_tab(100))
    print("climb_stairs(10)     =", climb_stairs(10))         # 89
    print("coin_change([1,3,4], 6)          =", coin_change([1, 3, 4], 6))     # 2
    print("coin_change([2], 3)              =", coin_change([2], 3))           # -1
    print("lis_quadratic([10,9,2,5,3,7,101,18]) =", lis_quadratic([10,9,2,5,3,7,101,18]))
    print("lis_nlogn([10,9,2,5,3,7,101,18])     =", lis_nlogn([10,9,2,5,3,7,101,18]))
    print("edit_distance('kitten', 'sitting')   =", edit_distance("kitten", "sitting"))  # 3
    print("knapsack([2,3,4,5], [3,4,5,6], 5)    =", knapsack([2,3,4,5], [3,4,5,6], 5))    # 7

Anatomy of the script

Name: @lru_cache(maxsize=None)

Desc: maxsize=None disables eviction, so distinct keys remain until cache clearing or destruction. Arguments must be hashable; an identity-hashable self can be cached, but mutations to fields are not included in the key. Cache correctness requires stable relevant state, not a blanket ban on methods.

Name: fib_tab uses two integer variables

Desc: Before loop iteration i, (a, b) = (F(i), F(i+1)). Simultaneous assignment reads both old values before rebinding. This saves stored states, though integers still grow in bits. Rolling storage works only when old dependencies and any required witness can safely be discarded.

Name: coin_change outer loop = amount, inner = coins

Desc: With positive coins, ascending amounts ensure dp[i-c] is available. This is minimum coin count with unlimited reuse. Swapping to coin-outer, ascending-amount-inner loops with the same min update still computes that minimum; it does not turn minimization into counting. Counting changes the update to addition, with ways[0]=1: amount-outer counts ordered sequences; denomination-outer counts unordered multisets when denominations are unique.

Name: lis_nlogn — patience sort

Desc: tails[k] is the minimum last value of any increasing subsequence of length k+1 in the processed prefix. Replacing a larger tail leaves more room to extend; inserting at the first tail ≥ x preserves strict-increase length. For [2, 3, 1], tails ends [1, 3], which is not an input-order subsequence. bisect_left is essential for strict LIS; bisect_right on [2, 2] instead permits length 2. Binary search plus O(1) replacement/amortized append gives O(n log n) comparisons.

Name: edit_distance — 2-D table with a border row/column

Desc: The border answers empty-prefix subproblems: dp[i][0]=i deletions and dp[0][j]=j insertions. Increasing i then j makes left, upper and upper-left cells available. Other 2-D DPs can need different base states; a zero border is not a universal recipe.

Name: knapsack iterates capacity BACKWARDS

Desc: So we don't accidentally use item i twice. Iterating forwards would be the unbounded-knapsack DP. Direction encodes ‘can I reuse items?’

What to observe

Use naive fib only at small n (the exercise uses 20). Compare its call count with memoized cache misses, not a promised number of seconds. For deeper n use fib_tab; fib_memo(1000) may raise RecursionError even with an unbounded cache, and this lab does not change interpreter recursion limits.

Both LIS functions return 4 on [10,9,2,5,3,7,101,18], for example from [2,5,7,101]. Trace the minimum-tail invariant, not an alleged reconstructed sequence.

Reverse knapsack's inner loop to range(w, capacity + 1) and the original capacity-5 demo still returns 7, not 8: weight 2 plus weight 3 is optimal in both variants. A discriminating one-item case is weights [2], values [3], capacity 4: descending gives 3; ascending gives 6 by reusing the item. Loop direction changes legality even when some outputs agree.

State, transition, base case and order for every program

The functions assume these domains rather than validating them. Negative amounts, nonpositive coins/weights and mismatched knapsack lists are not supported. For arbitrary-precision values, count arithmetic/comparison bit costs in addition to these elementary-operation bounds.

Goal: Convert a naive recursion into a memoised DP in under 60 seconds

Hint: This is the fastest way to feel the exponential-to-linear collapse.

Write this in a new file slow_fib.py:

import time, sys
# Prefer iteration for deep inputs; do not raise host recursion limits.
 
def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)
 
t0 = time.time(); print("fib(20) =", fib(20), "in", time.time() - t0, "s")

Run it and record the observed time; n=20 is intentionally small and has no 5–10 second guarantee. Add this import:

from functools import lru_cache

And ONE decorator above def fib(n)::

@lru_cache(maxsize=None)
def fib(n):
    ...

Exercise answer: attach the decorator to the actual recurrence, not a placeholder body. The complete bounded solution is:

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib_cached(n):
    if n < 2:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)
 
assert fib_cached(20) == 6765
assert fib_cached.cache_info().misses == 21

The earlier ellipsis snippet only shows where the decorator goes; it is not an implementation. The state-count claims assume single-threaded evaluation and an initially empty unbounded cache; concurrent calls can compute the same missing key more than once. Cache reuse reduces repeated work, but does not eliminate recursive depth. For n=1000 use the iterative fib_tab rather than increasing the host recursion limit.

(d) Production reality · 15 min

Edit distance is not every diff algorithm

Levenshtein distance assigns unit cost to insertion, deletion and substitution. Myers' 1986 shortest-edit-script paper instead works with insertions/deletions and exploits small edit distance D for O((m+n)D) work; replacing one unequal character is two edits in that model, not one. Git exposes Myers, minimal, patience and histogram choices, so “every code review uses the same DP” is false. The lesson is to match the state and cost model before comparing speed or output; a shortest script is not necessarily the most readable patch. The original mirror URL failed retrieval; the verified university mirror below contains the paper by Eugene W. Myers, not a replacement algorithm. Myers' original paper and Git's options are the governing references.

Routing values and preprocessing are different questions

A shortest-path value can be stated as a minimum over predecessor costs. With an edge-count limit, D[k,v] means the best cost to v using at most k edges; initialize the source to 0 and others to infinity, then relax from the previous edge-count layer. This supplies an acyclic dependency order even when the road graph is cyclic. Negative cycles need a separate treatment; nonnegative weights permit Dijkstra's greedy settling rule.

Precomputed shortcuts can accelerate repeated road queries, but that mechanism is not the same as claiming every maps provider uses one exact DP or reaches a universal microsecond latency. The original optional routing link is retained without renewing its vendor/performance assertions. State, weight assumptions and preprocessing/query trade-offs are what transfer from this lesson.

Exact finite-state decoding versus beam pruning

For a finite-state model, Viterbi can retain the best path ending in each state because that state summarizes future transition/emission possibilities. Beam search instead expands K partial hypotheses and keeps only K promising extensions; early pruning can discard the globally best sequence. In an autoregressive LLM, two same-length prefixes can imply different next-token distributions, so position alone is not sufficient state. Sampling and greedy decoding are other strategies: no claim about how every ChatGPT or Claude token is generated follows from this example. The D2L beam-search chapter describes the bounded search mechanism, not proprietary deployment internals.

Where this shows up in the rest of the plan

Root: DP threads through the entire series

Label: S034 · Greedy & Backtracking

Desc: The natural counter-strategies. Knowing when NOT to reach for DP.

Label: Application · Search algorithms (cross-topic, not a current S066 title)

Desc: Shortest-path methods reuse state values; Dijkstra requires nonnegative weights, while A* additionally relies on appropriate heuristic conditions for its exactness/settling behavior.

Label: Application · Reinforcement learning (not S095, which teaches model selection)

Desc: Bellman value equations express a recursive expected return. Q-learning uses sampled updates to learn action values; it is not simply the finite acyclic tabulation loop above.

Label: Application · NLP beam search (not S105, which teaches transfer learning)

Desc: Beam search keeps bounded partial hypotheses and can lose the optimum. Exact finite-state DP needs a sufficient state; token position alone is not sufficient for a general autoregressive model.

Label: S037 · SQL Joins

Desc: Join-order optimization can reuse best plans for subsets and required physical properties. Subset counts can be exponential, so optimizers need search limits; this is an application pattern, not a claim about every current engine.

Label: Application · System design (cross-topic, not a current S120 title)

Desc: Cache admission or autoscaling may be modelled as staged decisions if a sufficient state and cost model are available. The existence of choices alone does not make the production policy an exact DP.

Common DP anti-patterns to avoid

Memoising mutable relevant state — identity-hashable self remains a cache key, so changing fields can return a stale result. Unhashable lists/dicts instead raise TypeError. Include stable input state in the key or invalidate appropriately. Fill order wrong — using dp[i+1] before it's computed. Draw the dependency arrows before writing the loop. State too big — 3-D DPs where 2-D suffices, or including inputs that don't actually affect the answer. Prune the state before coding. Wrong state or budget — overlap alone cannot rescue an incorrect recurrence or exponentially many states. Lack of overlap can make memoization unnecessary even if the recurrence is valid.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Q: What are the two prerequisites a problem must satisfy for DP to apply?

A: Start with a correct recurrence and sufficient state; for optimization, justify optimal substructure under that state. Overlapping subproblems make reuse valuable. Counting DPs need no maximization, and a tree DP can combine each child just once. Neither overlap nor the label DP guarantees polynomial time.

Q: State the 4-step DP recipe.

A: (1) State — what parameters uniquely identify a subproblem. (2) Transition — how the answer at a state composes from smaller states. (3) Base case — the smallest states you know outright. (4) Order — the fill order that ensures dependencies are ready.

Q: Why is naive fib exponential and memoised fib linear?

A: Naive: the call tree has ~φⁿ ≈ 1.618ⁿ nodes because fib(k) is recomputed exponentially many times. Memoised: for an initially empty unbounded cache and n ≥ 2, n+1 states from 0 through n are evaluated once; later requests hit the cache. This is O(n) additions, not O(n) bit work on growing Python integers.

Q: When would you prefer tabulation over memoisation?

A: When the subproblem space is dense (you'll need almost all states anyway), when you want to avoid Python's recursion limit for deep problems, or when you want to apply a rolling-window space optimisation. Memo is easier to write; tabulation is easier to optimise.

Q: Why does 0/1 knapsack iterate capacity backwards in the 1-D optimisation?

A: So that dp[c - w] refers to the state before considering item i (which is what "0/1" means — use item at most once). Iterating forwards would let item i be used multiple times, silently converting the problem to unbounded knapsack.

Q: What is the state of the edit-distance DP, and what are the three transitions?

A: State: (i, j) = distance between a[:i] and b[:j]. Transitions when a[i-1] != b[j-1]: delete (dp[i-1][j] + 1), insert (dp[i][j-1] + 1), replace (dp[i-1][j-1] + 1). When characters match, dp[i][j] = dp[i-1][j-1] (no cost).

Q: You memoise a recursive function with @lru_cache but it's still slow. Give two possible causes.

A: (1) There may be exponentially many distinct sufficient states, excessive transition work or poor overlap; caching does not bound these. (2) A bounded cache can evict useful states, or irrelevant key parameters can prevent reuse. Inspect cache_info(). Unhashable arguments cause TypeError, not slow misses; mutable fields omitted from a hashable key cause stale answers, not guaranteed cache growth failure.

Q: Explain why lis_nlogn returns the correct LIS length but does NOT return the LIS itself.

A: tails is not the subsequence — it's the smallest-possible-tail of an LIS of length k+1 as we scan. Later replacements can overwrite earlier values while keeping the *length* invariant valid. To reconstruct one actual sequence, store suitable tail indices and predecessor pointers, or retain/recompute equivalent witness information.

Q: You have coins [1, 3, 4] and amount = 6. The greedy answer (take the biggest coin first) is 4 + 1 + 1 = 3 coins. The DP answer is 3 + 3 = 2 coins. What does this tell you about greedy vs DP?

A: Greedy is a local heuristic that assumes ‘best now’ leads to ‘best overall’. That's true for some problems (activity selection, fractional knapsack) and false for others (coin change with arbitrary denominations). When greedy fails, DP is the systematic alternative — it considers every choice at every step.

Q: Stretch — Solve ‘house robber’: given nums = [2, 7, 9, 3, 1], find the maximum sum you can rob without robbing two adjacent houses. Write the recurrence in one line and give the answer.

Stretch: true

A: Let H(k) be the best sum from the first k houses, allowing no robbery. Base H(0)=0, H(1)=max(0, nums[0]) when nonempty. For k≥2, H(k)=max(H(k−1), H(k−2)+nums[k−1]); ascending k ensures both dependencies exist. [2,7,9,3,1] gives 12 via positions 0,2,4. Empty input gives 0. Two rolling values suffice for the optimum, but reconstruction needs additional decisions or recomputation.

House robber: executable stretch answer

def house_robber(nums):
    two_back = one_back = 0
    for value in nums:
        two_back, one_back = one_back, max(one_back, two_back + value)
    return one_back
 
assert house_robber([2, 7, 9, 3, 1]) == 12
assert house_robber([]) == 0

This version allows the empty selection even if values are negative. It returns a value, not the house indices. The simultaneous assignment reads the prior H(k−2) and H(k−1) before rebinding.

Explain-out-loud test

1. What is dynamic programming? (one sentence that distinguishes state from storage)
2. What are the two things a problem needs for DP to work? (name both)
3. What is the 4-step recipe? (say all four in order)

Explain-out-loud answer guide

1. Dynamic programming computes a recurrence over well-defined states and reuses solved subproblems, via a cache or an ordered table, rather than recomputing equivalent histories.
2. A sufficient state and a correct recurrence come first; optimal substructure supports optimization, while overlap motivates caching. Then count states and transition work: reuse can still be exponential.
3. State what one entry means, derive its transition, define all base/unreachable cases, and choose an order that satisfies the dependencies. For coin change that means exact amount, last positive coin, zero/∞ bases, then ascending amounts.

What comes next

Next: S034 · Greedy & Backtracking — When to Use Each

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

• MIT 6.006 typed notes and Lecture 19 — original course on Fibonacci, shortest paths and DP modelling.
• Python 3.14 functools — hashable arguments, method self keys, unbounded cache and cache inspection.
• Python 3.14 bisect — left/right insertion boundaries used to distinguish strict and nondecreasing subsequences.
• Knapsack recurrence and loop order — author-maintained derivation of 0/1 versus complete knapsack.
• Myers 1986, Git diff options and D2L beam search — problem-specific production mechanisms and their limits.

Reviewed 2026-10-10 with exact-source finite CPU tests, including subset/subsequence oracles and discriminating mutations; no timing, deployment or site-wide approval is implied.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.