Unit 31: Dynamic Programming
Never solve the same thing twice.
Unit 31 of 31 in Python for kids. Its 6 lessons are Remembering Answers, Building From the Bottom, Counting the Ways, What to Take, Comparing Two Words and DP Master — below is everything each one explains, and a question or two from it to try.
Every sample on this page was run through real Python before it shipped, and prints exactly what it says it prints.
This unit opens with a fortnight’s trial of everything — no card needed — or with a family plan, bought in the iPhone app. The first two units of every track are free for ever. Try it in the app.
🧠 Remembering Answers
Write it down the first time
The fix for all that repeated work is embarrassingly simple: keep a dictionary of answers you have already worked out, and look there first. This is memoisation.
Python
def fib(n, memo):
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
print(fib(20, {}))
print(fib(50, {}))It prints
6765 12586269025
21,891 calls becomes 39
Same answer, same recursion — but nothing is worked out twice. And fib(50), which would have taken longer than a school term, returns instantly.
Python
calls = 0
def fib(n, memo):
global calls
calls = calls + 1
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
calls = 0
fib(20, {})
print(calls)It prints
39
Python will do it for you
@lru_cache is a decorator that adds memoisation to any function. This is what decorators are *for* — the same function, quietly given a memory.
Python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(50))
print(fib(90))It prints
12586269025 2880067194370816120
Try it yourself
When does memoisation help?
- Always
- When the same smaller problems come up more than once
- Only for Fibonacci
- When the function is slow
What does memoisation cost you?
- Nothing at all
- Memory — every remembered answer has to be kept somewhere
- Accuracy
- It makes code longer to run
Answer them in the app
🧱 Building From the Bottom
Start small and work upwards
Instead of asking for the big answer and recursing down, fill in a table starting from the smallest case. This is tabulation, and it needs no recursion at all.
Python
def fib(n):
table = [0] * (n + 1)
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table[n]
print(fib(20))
print(fib(50))It prints
6765 12586269025
You rarely need the whole table
Fibonacci only ever looks two steps back, so two variables will do. This is the same idea using almost no memory.
Python
def fib(n):
a = 0
b = 1
for _ in range(n):
a, b = b, a + b
return a
print(fib(10))
print(fib(50))It prints
55 12586269025
Climbing stairs
You can go up one or two steps at a time. The ways to reach step 5 are the ways to reach step 4 plus the ways to reach step 3 — because you arrive from one or the other.
Python
def ways(n):
table = [0] * (n + 1)
table[0] = 1
for i in range(1, n + 1):
table[i] = table[i - 1]
if i > 1:
table[i] = table[i] + table[i - 2]
return table[n]
for steps in [1, 2, 3, 4, 5]:
print(steps, ways(steps))It prints
1 1 2 2 3 3 4 5 5 8
Try it yourself
Those stair numbers — 1, 2, 3, 5, 8 — look familiar. Why?
- Coincidence
- It is Fibonacci: each answer is built from the two before it, exactly the same way
- Because stairs come in pairs
- They are the square numbers
What is the main advantage of tabulation over memoised recursion?
- It gives different answers
- No recursion, so no risk of running out of stack on a big problem
- It needs no table
- It is always shorter
Answer them in the app
🔢 Counting the Ways
Paths across a grid
Moving only right or down, the ways to reach a square are the ways to reach the one above plus the one to its left. Fill the grid in and the answer is in the corner.
Python
def paths(rows, cols):
grid = [[1] * cols for _ in range(rows)]
for r in range(1, rows):
for c in range(1, cols):
grid[r][c] = grid[r - 1][c] + grid[r][c - 1]
return grid[rows - 1][cols - 1]
print(paths(2, 3))
print(paths(3, 3))
print(paths(4, 4))It prints
3 6 20
Fewest coins to make an amount
For each amount, try every coin and keep the best. total + 1 stands in for "impossible", since no answer could ever really need that many coins.
Python
def fewest(coins, total):
impossible = total + 1
table = [0] + [impossible] * total
for amount in range(1, total + 1):
for coin in coins:
if coin <= amount:
table[amount] = min(table[amount], table[amount - coin] + 1)
if table[total] == impossible:
return -1
return table[total]
print(fewest([1, 2, 5], 11))
print(fewest([1, 3, 4], 6))
print(fewest([5], 3))It prints
3 2 -1
Counting ways rather than fewest
A small change asks a different question. Looping coins on the outside counts each *combination* once, so 1+2+2 and 2+1+2 are not counted twice.
Python
def ways(coins, total):
table = [1] + [0] * total
for coin in coins:
for amount in range(coin, total + 1):
table[amount] = table[amount] + table[amount - coin]
return table[total]
print(ways([1, 2, 5], 5))It prints
4
Try it yourself
Why does taking the biggest coin first not always work?
- It always works
- With coins 1, 3 and 4, greedily taking 4 then 1 then 1 gives three coins — but 3 and 3 is only two
- Big coins are worth less
- It works but is slow
What does this print?
Python
grid = [[1] * 3 for _ in range(2)]
for r in range(1, 2):
for c in range(1, 3):
grid[r][c] = grid[r - 1][c] + grid[r][c - 1]
print(grid)Answer them in the app
🎒 What to Take
A bag that will not hold everything
Each item has a weight and a value, and the bag has a limit. The knapsack problem asks for the most valuable load that fits — and greedily taking the most valuable thing first does not work.
Python
weights = [2, 3, 4]
values = [3, 4, 5]
print("bag holds 5")
print("greedy takes item 3 (value 5, weight 4), then nothing fits ->", 5)
print("best is items 1 and 2 (weight 5) ->", 3 + 4)It prints
bag holds 5 greedy takes item 3 (value 5, weight 4), then nothing fits -> 5 best is items 1 and 2 (weight 5) -> 7
Two questions per item
For every item and every possible bag size, ask: better to leave it, or to take it and use the rest of the space? The table remembers every answer.
Python
def knapsack(weights, values, capacity):
n = len(weights)
table = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
table[i][w] = table[i - 1][w]
if weights[i - 1] <= w:
taking = table[i - 1][w - weights[i - 1]] + values[i - 1]
table[i][w] = max(table[i][w], taking)
return table[n][capacity]
print(knapsack([2, 3, 4], [3, 4, 5], 5))It prints
7
A bigger bag never makes things worse
Reading along a row shows the best value climbing as the bag grows and then levelling off once everything worth taking already fits.
Python
def best_for_each_size(weights, values, capacity):
n = len(weights)
table = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
table[i][w] = table[i - 1][w]
if weights[i - 1] <= w:
table[i][w] = max(table[i][w], table[i - 1][w - weights[i - 1]] + values[i - 1])
return table[n]
print(best_for_each_size([2, 3, 4], [3, 4, 5], 9))It prints
[0, 0, 3, 4, 5, 7, 8, 9, 9, 12]
Try it yourself
What does table[i][w] mean?
- The weight of item i
- The best value using the first i items with a bag of size w
- How many items fit
- The value of item i
Answer it in the app
🔤 Comparing Two Words
The longest thing two words share
The longest common subsequence is the longest run of letters appearing in both, in the same order but not necessarily together. If the two letters match, the answer grows by one; if not, take the better of dropping one letter from either.
Python
def lcs(a, b):
table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1] + 1
else:
table[i][j] = max(table[i - 1][j], table[i][j - 1])
return table[len(a)][len(b)]
print(lcs("cat", "cart"))
print(lcs("ABCBDAB", "BDCABA"))It prints
3 4
How many edits to turn one word into another
Edit distance counts the changes needed — insert, delete or swap a letter. It is how spellcheckers guess what you meant.
Python
def edit(a, b):
table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(len(a) + 1):
table[i][0] = i
for j in range(len(b) + 1):
table[0][j] = j
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1]
else:
table[i][j] = 1 + min(table[i - 1][j], table[i][j - 1], table[i - 1][j - 1])
return table[len(a)][len(b)]
print(edit("cat", "cut"))
print(edit("kitten", "sitting"))It prints
1 3
Why this is the same idea as the knapsack
Both fill a grid where each square depends only on squares already filled in. That is what dynamic programming *is* — not a trick, a shape.
Python
print("knapsack : table[i][w] from table[i-1][...]")
print("edit : table[i][j] from table[i-1][...] and table[i][j-1]")
print("both : each square built from squares already done")It prints
knapsack : table[i][w] from table[i-1][...] edit : table[i][j] from table[i-1][...] and table[i][j-1] both : each square built from squares already done
Try it yourself
Why is the first row of the edit table 0, 1, 2, 3…?
- It is just a counter
- Turning an empty word into a word of length 3 takes 3 insertions
- To make the table square
- It could be anything
Answer it in the app
🏆 DP Master
Try it yourself
What does this print?
Python
table = [0] * 6
table[0] = 1
for i in range(1, 6):
table[i] = table[i - 1]
if i > 1:
table[i] = table[i] + table[i - 2]
print(table)Answer it in the app