The recurrence from the previous lesson is correct and, evaluated as written, makes 22 089 calls to answer a question about an amount of eighteen. With a memo it makes 50. The ratio is not a speed-up trick: it is the count of distinct subproblems, eighteen of them, against the number of times a memo-free recursion asks the same questions over again.
Core ideas
The hard idea is that the memo's saving is predicted, not discovered: it is the recursion tree's node count against the number of distinct arguments, and both are on the panel.
f(18) asks for f(17), f(16) and f(13); f(17) asks for f(16) again. The recursion tree has thousands of nodes and eighteen distinct arguments, because the argument is a single number between 1 and 18. A recursion whose arguments are all distinct — merge sort's halves, say — has nothing for a memo to save, which is why divide and conquer is not this.
Writing each answer down the first time makes every later request for the same argument a lookup. The measured calls fall from 22 089 to 50, and 50 is not mysterious: the memo holds eighteen entries and each is computed once from at most three sub-calls. The panel prints the ratio as the exact fraction 22089/50, because a decimal there would be a number that is merely close.
Filling bottom-up visits every (denomination, amount) pair in a fixed order, which is 76 cells for three denominations and an amount of eighteen, and it never calls itself. It does strictly more work than the memo — 76 cells against 18 memo entries — because it computes answers the recursion never asked for. What it buys is a fixed order, which is the subject of the next lesson and the thing that can be got wrong.
The material
Overlapping subproblems defined, the call counts measured, the arithmetic that predicts them, and the bound none of the counts establishes.
A recursive formulation has overlapping subproblems when the set of distinct arguments it is ever called with is much smaller than the number of calls it makes. The two numbers are both countable by running it, and their ratio is what a memo can save.
This is the second of the two properties a dynamic program needs, and it is the one about cost rather than about correctness. Optimal substructure says the recurrence is right. Overlapping subproblems says evaluating it naively is wasteful and that there is a specific, countable amount of waste to remove. A problem with the first and not the second is a divide-and-conquer problem, and a memo on it stores entries nothing ever reads.
The lab loads this instance. The memo-free recursion answers 5 after 22 089 calls. The same recursion with a memo answers 5 after 50 calls, and reports that it stored eighteen distinct subproblems. The table answers 5 after filling 76 cells and making 106 reads, with no recursion at all. Three routes, one answer, three costs a factor of hundreds apart.
Fifty is worth deriving rather than accepting. The memoised function is entered once per distinct argument that is genuinely computed — eighteen of them, plus the base case — and each such call makes one sub-call per denomination that fits. Every one of those sub-calls is itself a call. So the total is one call to start with, plus one call for every edge leaving a computed amount — and the amounts 1 through 18 have out-degrees 1, then 2 three times, then 3 fourteen times, which is 49. One and 49 is 50. Nothing about that figure is a property of the memo as a technique; it is the size of the dependency graph.
The memo stores eighteen entries; the table fills 76 cells. Those count different things. The memo's key is the remaining amount alone, because the recursion may use any denomination at any step; the table's cell is a (denomination-prefix, amount) pair, because it is filled in an order and each row makes one more denomination available. Four rows by nineteen columns is 76. Both are correct formulations of the same problem with different state, and the choice of state is the design decision this course keeps returning to.
For every amount a reachable from the coin set, the value the memoised recursion returns for a equals the value in the table's last row at column a, and both equal f(a).
By strong induction on a. Both agree at a = 0, where each is 0. Suppose both compute f correctly at every amount below a. The memoised recursion evaluates 1 + min of f(a − c) over the denominations that fit, using stored values that are correct by hypothesis, so it returns f(a) by the theorem of the previous lesson.
The table's last row at column a takes the minimum over the same set of options, reached as a row of cells rather than as a set of calls: the cell for denomination prefix i and amount a is the better of the cell above it and one more than the cell c columns to its left in its own row. Unfolding that row from left to right gives exactly the same minimum. Both therefore equal f(a), and the memo's smaller entry count is a difference of state, not of answer.
□
The panel prints 22089/50 and its decimal to one place, and the exact fraction is there because the ratio is a count divided by a count and rounding it would misrepresent two integers as one estimate. It is a measurement on one amount with one coin system. The proved statement is different in kind: the table is Θ(nk) for n denominations and amount k, and the memo-free recursion's call count grows exponentially in k because the recursion tree branches at least twice at every level whenever two denominations fit.
The two statements diverge in a way this page can show you. At an amount of six with coins 1, 3 and 4 — the previous lesson's instance — the memo-free recursion makes 24 calls and the table fills 28 cells, so the exponential method is ahead. At eighteen with 1, 2 and 5 the same two routes cost 22 089 and 76. Nothing changed about either bound between those two runs. What changed is which side of the crossing the input sits on, and no count on either side of it is a statement about the other.
The plot beside the grid makes the shape visible: call counts against the amount, on a logarithmic axis, with a dashed reference curve. It stops at sixteen whatever the amount is set to, because the unmemoised arm is re-run at every point on every redraw and plotting further would cost a few million calls for a picture that has already made its point. The figure above the plot is the full amount.
Interactive
The same definition run without a memo, with one, and as a table
Method
Both inputs to that decision are countable before any code is rewritten.
Not the calls — the arguments. Here it is the remaining amount, so there are k + 1 of them. If that count is comparable to the number of calls, there is nothing to save and a memo is overhead.
Put a counter in the function and run it on the instance you have. The ratio of the two counts is the saving available, and it is a measurement on that input rather than a property of the problem.
The memo keys on the amount alone; the table keys on the amount and how many denominations are in play. Both are correct. The first has eighteen entries and the second has 76 cells, and that difference is a design decision you are making whether or not you notice it.
A memo keyed on too little state returns a stored answer to a different question, and it does so silently and quickly. The only cheap defence is to run both on a small instance and compare, which is what the panel does on every keystroke.
The recursion is entered once per call, not once per distinct amount. Counting the top three levels of the unmemoised tree shows the duplication starting immediately.
The duplication is not an artefact of a badly written recursion. It is structural: the argument is one number, so any two paths down the tree that have spent the same total reach the same subproblem, and there are many such pairs. A memo is the observation that the tree was a directed acyclic graph with eighteen interior nodes all along.
The reconstruction on the panel is a separate claim and is checked separately: the coins it reports are re-added, and the count of them is compared with the answer. 5 + 5 + 5 + 2 + 1 is five coins adding to eighteen, and the panel says so rather than asserting that a reconstruction walked back correctly. Two lessons from here that check becomes the whole point of a page.
For a faded rehearsal, set the coins to 4 and 7 and the amount to 17. The supplied first move: 17 is odd and 4 is even, so any solution uses an odd number of 7s, which means one or three of them, leaving 10 or a negative amount. Decide what the panel will print before you look, and note that the answer is a result and not an error.
You should be able to count the distinct arguments a recursion can take, count its calls by running it, explain the gap between the memo's entries and the table's cells as a choice of state, and name a recursion for which a memo would be pure overhead.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.