Why remembering answers saves work
Memoisation (spelt memoization in the US) means saving the answer to a call so that you never work it out twice. It can turn a recursion that would take longer than a lifetime into one that finishes at once.
A delivery app prices a route by combining the prices of shorter routes. Many routes share the same shorter parts. Working each part out once, then looking it up, is the whole idea.
By the end of this lesson
Note
I can speed up a slow recursion by remembering answers.
Key words
| Word | What it means |
|---|---|
| Memoisation | saving the answer of a call to reuse it |
| Memo | the dictionary that holds the saved answers |
| Sub-problem | a smaller version of the problem |
| Dynamic programming | filling a table of answers, smallest first |
| Greedy | always taking the best-looking choice right now |
| Exponential | growth that multiplies at each step |
The cells students fill in are left blank in this preview.
Plain recursion repeats the same sub-problems
In the last lesson fib made 2,692,537 calls to answer fib(30). Most of those calls repeat work.
The diagram shows fib(5). The call fib(3) appears twice and fib(2) three times. Each repeat does the same work again, and the repeats multiply as n grows.
A memo dictionary stops the repeats
The fix is a memo: a dictionary from the input to its answer. Before working anything out, check the memo. If the input is there, return the saved answer.
If not, work it out, save it in the memo, then return it. Each input is now worked out once.
Run Fibonacci with a memo
# The same Fibonacci, but each answer is saved in a dictionary.
calls = [0]
memo = {}
def fib(n):
calls[0] = calls[0] + 1
if n < 2:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print("fib(30) =", fib(30), "calls", calls[0])
# Change 30 to 10 and run again.
Worked example: calls with and without a memo
| n | Plain calls | With a memo |
|---|---|---|
| 10 | 177 | 19 |
| 30 | 2,692,537 | 59 |
| 80 | more than 75 quadrillion | 159 |
The cells students fill in are left blank in this preview.
Write the memo version to a file
printf 'memo = {}\n\ndef fib(n):\n if n < 2:\n return n\n if n in memo:\n return memo[n]\n memo[n] = fib(n - 1) + fib(n - 2)\n return memo[n]\n\nprint(fib(80))\n' > fibmemo.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Ask for the 80th Fibonacci number
python3 fibmemo.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The fewest coins is a sub-problem puzzle
You must pay an amount with the fewest coins, using each coin as often as you like. The best answer for an amount is one coin plus the best answer for what is left.
So try each coin, look up the best answer for the rest, and keep the smallest. The same smaller amounts come up again and again, which suits a memo.
Worked example: coins 1, 4 and 5
| Amount | Fewest coins | Which coins |
|---|---|---|
| 0 | 0 | None |
| 1 | 1 | 1 |
| 3 | 3 | 1, 1, 1 |
| 4 | 1 | 4 |
| 6 | 2 | 5, 1 |
| 8 | 2 | 4, 4 |
The cells students fill in are left blank in this preview.
Fill the table from the bottom up
# Fewest coins for every amount from 0 up to 8, using coins 1, 4 and 5.
coins = [1, 4, 5]
amount = 8
best = [0]
for a in range(1, amount + 1):
fewest = -1
for coin in coins:
if coin <= a:
before = best[a - coin]
if before != -1:
if fewest == -1 or before + 1 < fewest:
fewest = before + 1
best.append(fewest)
print(best)
print("fewest coins for", amount, "is", best[amount])
# Change coins to [2, 5] and amount to 7, then run again.
A common mistake
Warning
Many people think the best answer comes from always taking the biggest coin first. That works for some coin sets and fails for others: for 8 with coins 1, 4 and 5 it gives four coins, not two. Try every coin and keep the best, saving each answer.