Phase 19 - Lesson 19.7

Dynamic Programming: Memoization and Tabulation

Optimal substructure, overlapping subproblems, top-down vs bottom-up - and, as a payoff, combinatorial game theory via Sprague–Grundy.

⏱ 70 min● Intermediate🔗 Prereqs: 19.6 recurrences; recursion

↖ Phase 19 hub

Builds on: 19.6 wrote the recurrence; DP is how you EVALUATE it without exponential blow-up.
Leads to: 19.8 compresses DP states into bitmasks; 19.11 counts partitions by DP; 19.13 accelerates linear DPs. The Euler Lab’s Dynamic Programming path is the direct drill ground.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Identify optimal substructure and overlapping subproblems, and explain why both are required for DP.
Convert an exponential recursion into a memoized \(O(\text{states}\times\text{transitions})\) algorithm and count that cost.
Write the same DP bottom-up (tabulation), choose a valid evaluation order, and reduce memory by rolling arrays.
Reconstruct an optimal solution (not just its value) from the DP table via parent pointers.
Compute Grundy numbers for an impartial game and use the Sprague–Grundy theorem to decide winning positions.

Key Vocabulary

Optimal substructure: An optimal solution is built from optimal solutions of subproblems. Without it, DP is simply invalid.

Overlapping subproblems: The naive recursion revisits the same subproblem exponentially often; caching collapses the recursion tree into a DAG.

Memoization: Top-down recursion + a cache. Computes only the reachable states; easiest to write from a recurrence.

Tabulation: Bottom-up filling of an array in a topological order of the dependency DAG. Faster constants, easy memory reduction.

State space: The set of distinct arguments the recurrence takes. DP cost = |states| × cost per transition. Designing the state IS the problem.

Grundy number (nim-value): \(g(v)=\operatorname{mex}\{g(u): v\to u\}\); a position is losing for the player to move iff its Grundy value is 0.

mex: Minimum EXcludant: the smallest non-negative integer not in a set. \(\operatorname{mex}\{0,1,3\}=2\).

Intuition & Motivation

Intuition

Naive recursion on Fibonacci calls \(F(30)\) thousands of times because it forgets. DP is the observation that the recursion tree, once you identify equal arguments, is really a small directed acyclic graph of states - and a DAG can be evaluated once per node. Everything else (top-down vs bottom-up, rolling arrays, reconstruction) is engineering. The intellectual work is always the same two questions: what is a state? and what are the transitions out of it?

The two conditions

DP applies exactly when the problem has (i) optimal substructure - an optimal answer decomposes into optimal answers to subproblems - and (ii) overlapping subproblems - those subproblems recur. Without (i), caching is wrong; without (ii), caching is pointless (that is plain divide-and-conquer, e.g. mergesort).

\[\text{cost}_{\mathrm{DP}} = |\text{states}| \times \text{transitions per state},\qquad\text{memory}=|\text{states}|\ (\text{or one layer, with a rolling array}).\] (19.15)

Formula (19.15) is the entire complexity analysis of every DP you will ever write, and it is what makes the feasibility check of 19.14 mechanical: count states, count transitions, multiply, compare to \(10^8\).

From recurrence to table: coin change

How many ways can you make \(n\) from an unlimited supply of coins \(c_1,\dots,c_k\) (order irrelevant)? The subtlety is avoiding double-counting permutations of the same multiset. Fix it in the loop order: iterate coins in the OUTER loop, amounts in the inner.

\[W[0]=1;\qquad \text{for each coin } c:\ \ \text{for } a=c..n:\ \ W[a] \mathrel{+}= W[a-c].\] (19.16)

Reading (19.16) as a generating function (19.6): \(\prod_{i}\frac{1}{1-x^{c_i}}\), and the loop is literally multiplying the series one factor at a time. DP and generating functions are the same computation in two notations.

Worked Example - Ways to make 200 from British coins

Coins: 1, 2, 5, 10, 20, 50, 100, 200 (pence). State = amount \(a\in[0,200]\); transitions = one per coin.

Initialise \(W[0]=1\) (one way to make nothing: use no coins), \(W[a]=0\) otherwise.

Process coin 1: every \(W[a]\) becomes 1 (only the all-1s way). Process coin 2: \(W[a] \mathrel{+}= W[a-2]\) for \(a=2..200\), which counts multisets using 1s and 2s.

Continue through 5, 10, 20, 50, 100, 200. Because each coin is fully absorbed before the next is introduced, each multiset is counted exactly once (its coins are added in the fixed coin order).

Result: \(W[200]=73682\). Cost: \(8\times200=1600\) additions - against a brute-force enumeration of astronomically many coin sequences.

Swap the loops (amounts outer, coins inner) and you count ordered compositions instead: a different (also useful) number. The loop order is not a style choice; it is the model.

Memoization vs tabulation

	Memoization (top-down)	Tabulation (bottom-up)
How	Recursion + cache (@lru_cache)	Loop filling an array
States computed	Only reachable ones	All of them
Order	Implicit (call stack)	You must find a valid topological order
Memory	Cache + recursion stack (can overflow)	Array; often reducible to one rolling layer
Use when	Sparse/irregular states, easy transcription from the recurrence	Dense states, tight constants, memory pressure

Reconstruction: the answer, not just its value

A DP that returns 42 is often half a solution. Store, alongside each state’s value, the transition that achieved it (a parent pointer), then walk backwards from the final state. This costs \(O(|\text{states}|)\) extra memory and turns ‘the maximum path sum is 1074’ into ‘here is the path’.

Payoff: combinatorial game theory

Impartial games (both players have the same moves; last player to move wins) are DP in disguise. Label each position by its Grundy number:

\[g(v)=\operatorname{mex}\{\,g(u)\ :\ v\to u\ \text{is a legal move}\,\},\qquad \operatorname{mex}(S)=\min(\Z_{\ge0}\setminus S).\] (19.17)

Theorem - Sprague–Grundy

Every position of a finite impartial game under the normal play convention is equivalent to a single Nim heap of size \(g(v)\). The position is a loss for the player to move iff \(g(v)=0\). For a disjoint sum of independent games, \(g(\text{sum})=g_1\oplus g_2\oplus\cdots\) (bitwise XOR).

The proof is an induction: from a position with \(g=0\) every move leads to \(g\ne0\) (else mex would not be 0), and from \(g\ne0\) some move reaches \(g=0\). That is exactly the definition of a losing/winning position. The XOR rule is where 19.8’s bit tricks meet game theory.

Coding workbench

The Euler Lab’s Dynamic Programming path is where this lesson gets cashed in: path sums through grids and triangles, coin and partition counting, digit DP, and a family of two-player games whose ‘who wins?’ questions are exactly (19.17).

Common Mistakes to Avoid

Caching a state that is not actually determined by its key - e.g. memoizing on \((i)\) when the answer also depends on remaining capacity. Silent wrong answers follow.
Getting the loop order wrong in coin change and counting orderings instead of multisets (or vice versa).
Recursing deeply in Python without raising the recursion limit - or better, rewriting bottom-up.
Using DP on a problem with no optimal substructure (e.g. longest simple path in a general graph, which is NP-hard). Overlap is not enough.
Assuming a position with a winning move has \(g=1\). Any \(g\ne0\) is a win; the specific value only matters when you XOR several games together.

Quant Practitioner Tips

Design the state first, on paper. If \(|\text{states}|\times\text{transitions}\gt 10^8\), no amount of coding skill will save you - go back and find a smaller state (19.8 and 19.14).
functools.lru_cache turns a correct recursion into a correct DP in one line. Write the recursion, verify it on small inputs by brute force, THEN add the decorator.
Rolling arrays: if \(dp[i]\) depends only on \(dp[i-1]\), keep two rows and drop memory from \(O(nm)\) to \(O(m)\).
For games, tabulate Grundy values for small \(n\) and LOOK at them. Patterns (like ‘losing iff \(n\equiv0\bmod4\)’) are usually visible immediately and then provable by induction.

Practice this in the Euler Lab

Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.

Warm-up:
#16 Power Digit Sum (1%, tier A) #20 Factorial Digit Sum (1%, tier A) #30 Digit Fifth Powers (2%, tier A) #14 Longest Collatz Sequence (3%, tier A)

Applied:
#313 Sliding Game (16%, tier B) #265 Binary Circles (17%, tier B) #816 Shortest Distance Among Points (17%, tier B)

Challenge:
#220 Heighway Dragon (41%, tier C) #666 Polymorphic Bacteria (41%, tier C)

276 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.

Knowledge Check

Q1 Hard

DP requires overlapping subproblems AND optimal substructure. What goes wrong if only overlap holds?

Nothing

The cache gives wrong answers, because an optimal whole may not be built from optimal parts

It becomes too slow

Memory blows up

Q2 Medium

In the coin-change count (19.16), why must the coin loop be outside the amount loop?

For speed

Because otherwise you count ordered sequences (compositions) rather than multisets, overcounting 1+2 and 2+1 separately

To avoid overflow

It doesn't matter

Q3 Medium

A position in an impartial game has Grundy value 0. The player to move:

Wins with correct play

Loses with correct play

Wins only if the heap is even

Can force a draw

Practical Exercise

(a) Give the state, transitions, and complexity for the 0/1 knapsack with \(n\) items and capacity \(W\), and explain why this is only ‘pseudo-polynomial’. (b) Compute the Grundy values of the subtraction game with moves \(\{1,3,4\}\) for \(n=0..10\) and identify the losing positions. (c) Show how to reduce the knapsack’s memory from \(O(nW)\) to \(O(W)\), and explain the direction the inner loop must run.

▶ Show full solution

(a) State: \((i,w)\) = considering the first \(i\) items with remaining capacity \(w\); value \(V[i][w]\) = best achievable value. Transition: \(V[i][w]=\max\big(V[i-1][w],\ v_i+V[i-1][w-w_i]\ \text{if } w_i\le w\big)\). Cost \(O(nW)\) time, \(O(nW)\) memory. It is pseudo-polynomial because \(W\) is a numeric value, not an input length: writing \(W\) takes only \(\log W\) bits, so \(O(nW)\) is exponential in the input size. That is why knapsack is NP-hard despite this DP.

(b) Moves \(\{1,3,4\}\). \(g(0)=0\). \(g(1)=\mathrm{mex}\{g(0)\}=\mathrm{mex}\{0\}=1\). \(g(2)=\mathrm{mex}\{g(1)\}=\mathrm{mex}\{1\}=0\). \(g(3)=\mathrm{mex}\{g(2),g(0)\}=\mathrm{mex}\{0,0\}=1\). \(g(4)=\mathrm{mex}\{g(3),g(1),g(0)\}=\mathrm{mex}\{1,1,0\}=2\). \(g(5)=\mathrm{mex}\{g(4),g(2),g(1)\}=\mathrm{mex}\{2,0,1\}=3\). \(g(6)=\mathrm{mex}\{g(5),g(3),g(2)\}=\mathrm{mex}\{3,1,0\}=2\). \(g(7)=\mathrm{mex}\{g(6),g(4),g(3)\}=\mathrm{mex}\{2,2,1\}=0\). \(g(8)=\mathrm{mex}\{g(7),g(5),g(4)\}=\mathrm{mex}\{0,3,2\}=1\). \(g(9)=\mathrm{mex}\{g(8),g(6),g(5)\}=\mathrm{mex}\{1,2,3\}=0\). \(g(10)=\mathrm{mex}\{g(9),g(7),g(6)\}=\mathrm{mex}\{0,0,2\}=1\).

Sequence \(g(0..10)=0,1,0,1,2,3,2,0,1,0,1\); losing positions (\(g=0\)) are \(n\in\{0,2,7,9\}\), and the pattern is periodic with period 7 from \(n=0\).

(c) Keep a single array \(V[w]\) and process items one at a time, iterating \(w\) downwards from \(W\) to \(w_i\): \(V[w]=\max(V[w],\ v_i+V[w-w_i])\). Descending order guarantees that \(V[w-w_i]\) still holds the value from the previous item row, so each item is used at most once. Ascending order would allow re-using the same item (which is exactly the unbounded-knapsack DP - the same loop-order lesson as (19.16)).

After the reveal, answer for yourself: Both (a) and (c) hinge on the loop direction. Write down, in one sentence, the invariant that the loop direction is protecting.

Lesson Summary

DP = identify the state, evaluate the DAG once per node. Its cost is always |states| × transitions, which is what makes feasibility mechanical. Memoization (top-down) is the easiest transcription of a recurrence; tabulation (bottom-up) gives tighter constants and rolling-array memory reductions; parent pointers recover the actual solution. Sprague–Grundy is DP applied to games: \(g(v)=\mathrm{mex}\{g(u)\}\), with \(g=0\) a loss for the mover and XOR combining independent games.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: What are the two conditions for DP, and which one is about correctness?
A: Optimal substructure (correctness - an optimal whole is built from optimal parts) and overlapping subproblems (efficiency - the same subproblem recurs, so caching pays).

Q: State the Sprague–Grundy rule for a position and for a sum of games.
A: \(g(v)=\mathrm{mex}\{g(u):v\to u\}\); the position is a loss for the player to move iff \(g(v)=0\). For independent games played side by side, the Grundy value is the bitwise XOR of the components.

Completion Checklist

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

The Pragmatic Programmer (Thomas & Hunt, 2nd/20th Anniv. ed., 2019) current - Ch. 5 & Ch. 7 - Decomposition, caching and the discipline of testing a DP against a brute-force oracle on small inputs - the only reliable way to catch a wrong state definition.
Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Ch. I.4 - Induction: every DP correctness proof, and the Sprague–Grundy theorem itself, is an induction on the size/height of the state DAG.
The Elements of Statistical Learning (Hastie, Tibshirani & Friedman, 2nd ed.) current - Ch. 9–10 - Dynamic programming as the computational engine behind sequential models (e.g. Viterbi-type recursions) - the same state/transition accounting in a statistical setting.

← 19.6 Next: 19.8 →