The close of the previous lesson left a question hanging: what do we do when a problem has optimal substructure but the greedy bet fails — when paying 6 € requires realizing that 3+3 beats starting with the 4? The answer is dynamic programming (DP): instead of betting everything on one decision, we consider all the possible decisions... but without paying the exponential price of brute force, because the repeated subproblems are computed once and stored. It is exactly the idea we noted in 02-02 with build_index — spending memory to avoid repeating work — elevated to a design strategy. In this lesson we will develop it in its two flavors (memoization and tabulation), apply it to two RutaBus problems — the cheapest trip with per-segment fares and the selection of fleet upgrades with a limited budget — and learn not only to compute the optimal value, but to reconstruct the solution that achieves it.
Contents
- The two ingredients: overlapping subproblems and optimal substructure
- Fibonacci: the minimal example of the disaster and its cure
- Memoization (top-down): remembering what's already computed
- RutaBus problem: the cheapest trip with per-segment fares
- Tabulation (bottom-up): filling the table without recursion
- Top-down vs bottom-up
- The 0/1 knapsack: fleet upgrades on a limited budget
- Reconstructing the solution, not just the value
The two ingredients: overlapping subproblems and optimal substructure
Dynamic programming applies when the problem has, at the same time:
- Optimal substructure: the optimal solution of the problem is built from optimal solutions of its subproblems. (The same property greedy demanded in 03-02 — no coincidence: greedy is, in a way, a DP that dares to explore a single branch.)
- Overlapping subproblems: when decomposing the problem, the same subproblems appear again and again. Here lies the key difference with divide and conquer (03-01), whose subproblems were independent: if there is no overlap, storing results saves nothing.
| Strategy | Optimal substructure | Subproblems | Decisions explored |
|---|---|---|---|
| Divide and conquer | (not necessarily an optimization) | Independent | — |
| Greedy | Yes | One after another | One (the greedy one) |
| Dynamic programming | Yes | Overlapping | All (storing results) |
Fibonacci: the minimal example of the disaster and its cure
Before boarding the bus, the smallest possible example of overlapping subproblems: the Fibonacci sequence (1, 1, 2, 3, 5, 8, ...), where each term is the sum of the two before it.
In 02-01 we learned to analyze recursive functions by counting calls. Let's count them: fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) — again! — and fib(2)...
flowchart TD
A["fib(5)"] --> B["fib(4)"]
A --> C["fib(3)"]
B --> D["fib(3) (repeated!)"]
B --> E["fib(2)"]
C --> F["fib(2)"]
C --> G["fib(1)"]
D --> H["fib(2)"]
D --> I["fib(1)"]
fib(3) is computed 2 times here; in fib(50), fib(3) would be computed billions of times. The call tree grows like O(2ⁿ) — the worst category of the hierarchy of 01-03 — for a problem that only has n distinct subproblems: fib(1), fib(2), ..., fib(n). All the excess is repeated work. The cure: compute each one once and jot it down.
Memoization (top-down): remembering what's already computed
Memoization = wrapping the recursion with a "notebook" (normally a dictionary) where each result is written down the first time it is computed; the following times, the note is returned in O(1) — the dictionary lookup whose cost we studied with build_index in 02-02.
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo: # already computed? -> O(1)
return memo[n]
if n <= 2:
return 1
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]Analysis with the tools from Module 2:
- Time: each
fib_memo(k)is computed for real only once (afterwards it stays inmemo). There are n subproblems and each does O(1) work outside the recursions: O(n). From exponential to linear. - Space: the dictionary holds n entries and the recursion stack reaches depth n (02-02): O(n).
This is, by name and surname, the time ↔ space trade-off we anticipated in 02-02: we pay O(n) of memory to collapse the time from O(2ⁿ) to O(n). Rarely in computing do you buy so much for so little.
Practical note: Python ships memoization out of the box with
from functools import lru_cacheand the@lru_cache(maxsize=None)decorator on the recursive function. Use it in production; here we write the notebook by hand to see the mechanism.
RutaBus problem: the cheapest trip with per-segment fares
Now a real RutaBus problem. On line L2 there are n + 1 stops numbered from 0 (Main Square) to n (River Park). From each stop i the passenger can:
- advance 1 stop paying
fare1[i]cents, or - advance 2 stops (semi-express service) paying
fare2[i]cents.
What is the minimum cost to go from stop 0 to stop n?
# Example with n = 5 (stops 0..5)
fare1 = [120, 140, 100, 130, 110] # fare1[i]: from i to i+1
fare2 = [210, 220, 260, 180] # fare2[i]: from i to i+2Step 1 — define the subproblem. Let cost(i) = minimum cost to get from stop i to stop n. We want cost(0).
Step 2 — the recurrence (optimal substructure). From i there are only two possible first decisions; whatever comes after must, in turn, be optimal:
cost(n) = 0 (we have arrived)
cost(n-1) = fare1[n-1] (only the 1-stop hop fits)
cost(i) = min(fare1[i] + cost(i+1),
fare2[i] + cost(i+2))Step 3 — check the overlap. cost(3) is needed both by cost(2) (hopping 1) and by cost(1) (hopping 2): the same subproblems appear via different paths, just like in Fibonacci. Without memory, the recursion would be exponential; with it, there are only n + 1 subproblems.
Top-down version (memoization):
def min_cost_memo(fare1, fare2, i=0, memo=None):
n = len(fare1) # number of segments = number of stops - 1
if memo is None:
memo = {}
if i in memo:
return memo[i]
if i == n: # base case: we have arrived
return 0
if i == n - 1: # next-to-last stop: only the 1-hop
return fare1[i]
hop1 = fare1[i] + min_cost_memo(fare1, fare2, i + 1, memo)
hop2 = fare2[i] + min_cost_memo(fare1, fare2, i + 2, memo)
memo[i] = min(hop1, hop2)
return memo[i]
print(min_cost_memo(fare1, fare2)) # 490Time O(n) — each stop is solved only once — and space O(n) between the memo and the recursion stack.
Tabulation (bottom-up): filling the table without recursion
Tabulation turns the computation around: instead of starting from the big question and going down (top-down), it starts from the base cases and goes up, filling a table with a loop. No recursion, no stack.
def min_cost_tab(fare1, fare2):
n = len(fare1)
cost = [0] * (n + 1) # cost[i]: minimum from i to n
cost[n] = 0 # base cases
cost[n - 1] = fare1[n - 1]
for i in range(n - 2, -1, -1): # from stop n-2 down to 0
cost[i] = min(fare1[i] + cost[i + 1],
fare2[i] + cost[i + 2])
return cost
print(min_cost_tab(fare1, fare2))
# [490, 400, 280, 180, 110, 0]Let's fill the table by hand, cell by cell and in the same order as the loop — manually verifying two or three cells is the cheapest unit test in existence for a DP:
| i | computation | cost[i] |
|---|---|---|
| 5 | base case (destination) | 0 |
| 4 | base case: fare1[4] = 110 |
110 |
| 3 | min(fare1[3]+cost[4], fare2[3]+cost[5]) = min(130+110, 180+0) = min(240, 180) |
180 |
| 2 | min(100+cost[3], 260+cost[4]) = min(100+180, 260+110) = min(280, 370) |
280 |
| 1 | min(140+cost[2], 220+cost[3]) = min(140+280, 220+180) = min(420, 400) |
400 |
| 0 | min(120+cost[1], 210+cost[2]) = min(120+520... careful, cost[1] is 400!) = min(120+400, 210+280) = min(520, 490) |
490 |
The minimum cost is 490 cents. Look at cell i = 3: there the semi-express (180) beats the single hop (240); by contrast at i = 2 the single hop is better. The table takes, for each stop, the best decision — no irrevocable bets whatsoever.
Time O(n), space O(n) for the table — and notice: since cost[i] only consults i+1 and i+2, two variables would suffice, bringing the auxiliary space down to O(1). That kind of memory reduction is studied in Module 5 (05-02); here it is enough to know it exists.
Top-down vs bottom-up
| Aspect | Memoization (top-down) | Tabulation (bottom-up) |
|---|---|---|
| Shape | Recursion + dictionary | Loops + table (list/matrix) |
| Order of computation | Whatever the recursion dictates | Explicit, from base cases upward |
| Subproblems computed | Only the truly needed ones | All those in the table |
| Recursion stack | Yes — risk of RecursionError with large n (02-02) |
No |
| Ease of writing | Almost direct from the recurrence | Requires thinking out the fill order |
| Optimizing space | Hard | Easy (keep just the last rows) |
Practical rule: always design the recurrence first (it is the heart of DP); then write the memoization to validate it fast, and convert it to tabulation if you need performance, control over space, or to avoid the stack.
The 0/1 knapsack: fleet upgrades on a limited budget
DP's star problem, in RutaBus form. Management approves a budget of 9 (thousands of euros) and the technical team proposes four upgrades, each with its cost and its estimated benefit (service improvement index):
upgrades = [
("Onboard wifi", 2, 3), # (name, cost, benefit)
("Accessibility ramp", 3, 4),
("Information panels", 4, 5),
("Eco climate control", 5, 8),
]
BUDGET = 9Each upgrade is either fully funded or not funded at all (hence "0/1": no half wifi). Goal: maximize the total benefit without exceeding the budget. The greedy by benefit/cost ratio fails in general (it's coin change all over again); DP solves it exactly.
Subproblem: V[i][p] = maximum benefit using only the first i upgrades with budget p.
Recurrence: for the i-th upgrade, with cost c and benefit b:
V[i][p] = V[i-1][p] if c > p (doesn't fit)
V[i][p] = max(V[i-1][p], (option A: don't fund it)
V[i-1][p-c] + b) (option B: fund it)def upgrade_knapsack(upgrades, budget):
n = len(upgrades)
# (n+1) x (budget+1) table initialized to 0 (row 0 = no upgrades)
V = [[0] * (budget + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
name, c, b = upgrades[i - 1]
for p in range(budget + 1):
if c > p: # doesn't fit
V[i][p] = V[i - 1][p]
else:
V[i][p] = max(V[i - 1][p], # without upgrade i
V[i - 1][p - c] + b) # with upgrade i
return V
V = upgrade_knapsack(upgrades, BUDGET)
print(V[len(upgrades)][BUDGET]) # 13The full table (rows: upgrades considered so far; columns: budget 0..9):
| p=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| ∅ (no upgrades) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| +Wifi (2, 3) | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| +Ramp (3, 4) | 0 | 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 | 7 |
| +Panels (4, 5) | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 9 | 12 |
| +Climate (5, 8) | 0 | 0 | 3 | 4 | 5 | 8 | 8 | 11 | 12 | 13 |
Let's read several cells to understand the mechanism — this is what turns the table into knowledge:
- Wifi row, p=2: the wifi finally fits (cost 2):
max(V[∅][2], V[∅][0] + 3) = max(0, 3) = 3. The whole row is 3 from there on: with a single upgrade available there is nothing more to squeeze. - Ramp row, p=3:
max(V[wifi][3], V[wifi][0] + 4) = max(3, 4) = 4. With budget 3, the ramp alone beats the wifi alone. - Ramp row, p=5:
max(V[wifi][5], V[wifi][5−3] + 4) = max(3, 3 + 4) = 7. Funding the ramp pays off because with the remaining budget (2) the wifi still fits: the cellV[wifi][2] = 3already contained that best prior decision. Each cell reuses optima already computed: optimal substructure in action. - Panels row, p=9:
max(V[ramp][9], V[ramp][9−4] + 5) = max(7, 7 + 5) = 12. Funding the panels (4) leaves 5, andV[ramp][5] = 7was "wifi + ramp": total wifi + ramp + panels = 12. - Climate row, p=9 — the final answer:
max(V[panels][9], V[panels][9−5] + 8) = max(12, 5 + 8) = 13. Funding the climate control leaves budget 4, whose prior optimum wasV[panels][4] = 5(the panels alone). The global maximum is 13.
Cost of the algorithm: two nested loops → O(n · P) in time and space (n upgrades, P budget), a direct analysis with the rules of 02-01. A fine point: that cost depends on the numeric value P, not just on how many elements there are — the DP knapsack is efficient for moderate budgets, not free in general.
Reconstructing the solution, not just the value
"The maximum benefit is 13" is of no use to management: they want to know which upgrades to fund. The table already contains that information — just walk it backwards, asking at each row "did this upgrade change the value?":
def reconstruct(upgrades, V, budget):
selection = []
p = budget
for i in range(len(upgrades), 0, -1): # from the last row to the first
if V[i][p] != V[i - 1][p]: # upgrade i was decisive
name, c, b = upgrades[i - 1]
selection.append(name)
p -= c # deduct its cost
return list(reversed(selection))
print(reconstruct(upgrades, V, BUDGET))
# ['Information panels', 'Eco climate control']Trace over the table above:
- Climate row, p=9:
V[4][9] = 13 ≠ V[3][9] = 12→ the climate control goes in; remaining budget: 9 − 5 = 4. - Panels row, p=4:
V[3][4] = 5 ≠ V[2][4] = 4→ the panels go in; remaining: 4 − 4 = 0. - Ramp row, p=0:
V[2][0] = 0 = V[1][0]→ the ramp changed nothing: out. - Wifi row, p=0:
V[1][0] = 0 = V[0][0]→ out.
Optimal selection: panels + climate control (cost 4 + 5 = 9, benefit 5 + 8 = 13). Note the counter-intuitive detail: the wifi, the upgrade with the best benefit/cost ratio (1.5), is not in the optimum — a ratio-based greedy would have grabbed it first and gotten trapped. DP saw it coming because it explored all the combinations... paying for each subproblem only once.
The same "look at which cell I came from" trick reconstructs the cheap L2 trip: at each stop i, if cost[i] == fare1[i] + cost[i+1] the optimum hopped 1 stop; otherwise, it hopped 2. With our table: 0 →(210)→ 2 →(100)→ 3 →(180)→ 5, total 490.
We close with the promised mention: DP also operates on whole graphs — Floyd-Warshall computes the shortest paths between all pairs of stops in the RutaBus network by filling a table of subproblems indexed by pairs of stops and allowed intermediate nodes. It is pure DP on graphs and we will study it in 04-06.
Common Mistakes and Tips
- Starting to code without writing the recurrence. DP is designed on paper: subproblem (what exactly does
V[i][p]mean?), recurrence, base cases. The code is the literal translation; without a clear recurrence, you'll get a tangle of indices. - Defining the subproblem wrong. If you cannot express the recurrence using only "smaller" subproblems, the definition is no good. Reformulate it — often by adding a parameter, like the knapsack's "using only the first i upgrades".
- Not verifying cells by hand. Pick 2-3 cells of the table, recompute them with the recurrence and turn them into test
asserts. Index errors (ivsi-1,pvsp-c) are silent and this is the net that catches them. - Forgetting the base cases or leaving the table uninitialized.
cost[n] = 0and the knapsack's ∅ row are not decoration: the whole table rests on them. - Using memoization with lists as keys. Dictionary keys must be immutable (
int,tuple); a list raisesTypeError. Convert the state to a tuple. - Recursion too deep. For n in the tens of thousands, memoization exhausts Python's stack (02-02): switch to tabulation.
- Applying DP where there is no overlap. If each subproblem appears only once, the memo saves nothing and only wastes memory: that is divide and conquer (03-01) and it needs no notebook.
Exercises
Exercise 1
A passenger at stop 0 can advance 1 or 2 stops at each step (no fares: here we only count paths). Write ways_to_reach(n) that counts in how many distinct ways they can arrive exactly at stop n, with memoization. Compute by hand the values for n = 1..5 and observe which sequence appears. What is the time and space cost?
Exercise 2
Convert ways_to_reach to tabulation and then reduce its auxiliary space to O(1) while keeping the O(n) time. (Hint: how many previous cells does each cell need?)
Exercise 3
A fifth option is added to the fleet upgrades problem: ("Fleet GPS", 4, 6). With budget 9, compute the new row of the table and reconstruct the optimal selection. Is the climate control still in the solution? And the panels?
Solutions
Solution 1
def ways_to_reach(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n == 0:
return 1 # a single way: the empty path
if n == 1:
return 1 # only one 1-hop
memo[n] = ways_to_reach(n - 1, memo) + ways_to_reach(n - 2, memo)
return memo[n]To reach n, the last hop came from n−1 or from n−2, and both sets of paths are disjoint: f(n) = f(n−1) + f(n−2). Values: f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(5)=8 — shifted Fibonacci. Our transport problem hides the same structure as the "toy" example: recognizing known recurrences under new disguises is one of DP's great skills. Time O(n), space O(n).
Solution 2
def ways_to_reach_tab(n):
if n <= 1:
return 1
prev2, prev1 = 1, 1 # f(0), f(1)
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1Each cell only needs the two before it, so the "table" compresses into two variables: time O(n), auxiliary space O(1) and no recursion stack. It is the time↔space trade-off of 02-02 tuned down to the bare minimum.
Solution 3
The new row is computed with V[5][p] = max(V[4][p], V[4][p−4] + 6) for p ≥ 4. In the final cell: V[5][9] = max(V[4][9], V[4][5] + 6) = max(13, 8 + 6) = 14. Reconstruction: V[5][9] = 14 ≠ V[4][9] = 13 → the GPS goes in, remaining 5; V[4][5] = 8 ≠ V[3][5] = 7 → the climate control goes in, remaining 0; nothing else fits. Optimal selection: GPS + climate control (cost 4 + 5 = 9, benefit 14). The climate control stays, but the panels drop out: adding one candidate can reorganize the entire solution — exactly what a greedy of irrevocable decisions could never do.
Conclusion
Dynamic programming is the strategy for problems with optimal substructure and overlapping subproblems: the full decision space is explored, but each subproblem is paid for only once, trading memory for time — the trade-off we had been announcing since 02-02, now with a name of its own. We have learned its design method (define the subproblem → write the recurrence → fix the base cases), its two realizations — top-down memoization and bottom-up tabulation —, and we have applied it to L2's cheapest trip (490 cents, and we know via where) and to the 0/1 knapsack of the fleet upgrades, including the reconstruction of the solution by walking the table backwards. With divide and conquer, greedy and DP we now have three ways to build solutions; we are missing the strategy for when there is no choice but to search: constraint problems where you must try combinations, detect dead ends and retrace your own steps. That systematic exploration with going back — backtracking — closes the module in the next lesson, where we will also put the four strategies face to face.