1
Overlap is what makes memoisation pay
Merge sort's subproblems are disjoint, so caching them saves nothing. Fibonacci's recur constantly.
Lesson · Algorithms and Complexity · Design
Dynamic Programming
When subproblems overlap, recomputing them is exponentially wasteful. Storing each answer turns an exponential recursion into a polynomial one, and the technique applies exactly when the problem has optimal substructure.
OPTIMAL SUBSTRUCTURE an optimal solution contains optimal sub-solutions
OVERLAPPING SUBPROBLEMS the same subproblem recurs
memoise (top down) or fill a table (bottom up)
naive Fibonacci: ~1.6ⁿ calls. With memoisation: n.
Two conditions, one technique
Core ideas
What this lesson establishes
Both conditions are needed. Optimal substructure without overlap is divide-and-conquer; overlap without optimal substructure is not helped.
2
Optimal substructure is what makes the recurrence valid
The best solution must be assemblable from best sub-solutions. Longest simple path fails this, and no dynamic program for it exists.
3
Top-down and bottom-up are the same computation
Memoised recursion computes only the subproblems it needs; a table computes all of them in dependency order. The complexity is the same.
The material
Dynamic programming
The two conditions, three worked examples, and the problem it cannot help.
The motivating case
The naive recursive Fibonacci makes about 1.6ⁿ calls because it recomputes the same values exponentially often: F(5) calls F(3) twice, F(2) three times, and so on. Storing each value when first computed reduces the count to n.
n naive calls memoised calls
10 177 10
30 2 692 537 30
50 ~ 40 000 000 000 50
Definition · The two conditions
Optimal substructure: an optimal solution is built from optimal solutions to subproblems. Overlapping subproblems: the recursion revisits the same subproblems many times.
Both are required. Merge sort has optimal substructure and no overlap, so it is divide-and-conquer and memoisation would help nothing. A problem with overlap and no optimal substructure cannot be solved by combining sub-solutions at all.
Coin change
best[0] = 0
best[v] = 1 + min{ best[v − c] : c a coin, c ≤ v }
coins {1,3,4}, target 6:
best[1]=1 best[2]=2 best[3]=1 best[4]=1 best[5]=2 best[6]=2
best[6] = 1 + min(best[5], best[3], best[2]) = 1 + 1 = 2
the two coins are 3 + 3 — which greedy missed
The recurrence is the optimal substructure written down: the best way to make v uses some coin c, and the rest must be the best way to make v − c. Filling the table costs Θ(v · |coins|), and the greedy failure of “Greedy Algorithms” disappears.
Longest common subsequence
L[i][j] = length of the longest common subsequence of the first i
characters of X and the first j of Y
L[i][j] = 0 if i = 0 or j = 0
= L[i−1][j−1] + 1 if X[i] = Y[j]
= max(L[i−1][j], L[i][j−1]) otherwise
Cost Θ(mn), against exponential for the naive recursion. This is the algorithm behind diff, behind version-control merges, and behind sequence alignment in bioinformatics.
Where it does not apply
Example · Longest simple path
Finding the longest path with no repeated vertex has no optimal substructure: the longest path from a to c need not consist of the longest path from a to b plus the longest from b to c, because those may share vertices and the concatenation would not be simple. The problem is NP-hard, and no dynamic program for it exists.
Contrast with the SHORTEST path, which does have optimal substructure — any subpath of a shortest path is shortest — and is solved in polynomial time by Graphs and Trees's Dijkstra. Two problems whose statements differ by one word, on opposite sides of tractability.
Top-down or bottom-up
MEMOISED (top down) recursion + a cache
computes only the subproblems needed
natural to write from the recurrence
TABULATED (bottom up) fill a table in dependency order
no recursion overhead
often allows the space to be reduced
The two have the same asymptotic cost. Bottom-up often permits dropping old rows of the table — the Fibonacci table needs only the last two entries — which is why it is preferred when memory matters.
Interactive
Algorithms and growth
Counts from running, not from quoting
Method
Designing a dynamic program
Recurrence first; the implementation follows.
1
Define the subproblem precisely
"The fewest coins making value v", "the LCS of the first i and first j characters". A vague subproblem gives no recurrence.
2
Write the recurrence
How an optimal solution decomposes. This is where optimal substructure is either present or absent.
3
Identify the base cases
The smallest subproblems, answered outright.
4
Choose memoisation or a table
Same cost. Bottom-up if the space can be reduced; top-down if only some subproblems are needed.
Dynamic programming
Score 0 / 0Choose the answer you can justify.
Coin change with {1, 3, 4}
Filling the table from 0 upward.
v: 0 1 2 3 4 5 6 7 8
best: 0 1 2 1 1 2 2 2 2
best[6] = 1 + min( best[5], best[3], best[2] )
= 1 + min( 2, 1, 2 ) = 2 via coin 3
best[7] = 1 + min( best[6], best[4], best[3] )
= 1 + min( 2, 1, 1 ) = 2 via coin 3 or 4
GREEDY at 6: 4 + 1 + 1 three coins
TABLE at 6: 3 + 3 two coins
Cost: Θ(v · number of coins) — here 6 × 3 = 18 comparisons.
Every entry was computed once and read several times, which is the whole saving. The naive recursion would recompute best[3] at values 4, 6 and 7, and each of those recomputations would recurse again.
Common mistakes
1
Applying it without checking optimal substructureThe recurrence will be written and will be wrong. Longest simple path is the standard example.
2
Memoising a divide-and-conquer algorithmMerge sort's subproblems never repeat, so the cache never hits and the overhead is pure loss.
3
Defining the subproblem loosely"The best solution so far" is not a subproblem. It must be a function of explicit parameters.
Check your understanding
✓
Finish when you can write the recurrence before any code.
Write the recurrence for the 0/1 knapsack problem — items with weights and values, a capacity, items cannot be split. Define the subproblem in terms of the first i items and remaining capacity w, and the recurrence writes itself.
Note: The name is historical and misleading: Bellman chose it in the 1950s partly because "programming" then meant planning and partly, by his own account, because it sounded impressive enough to survive a hostile funding review. It has nothing to do with programming in the modern sense.