Dynamic programming

Fibonacci, top-down memoised

This is the same recurrence and the same table as the bottom-up page, approached from the other end. Ask for F(n); it asks for F(n−1) and F(n−2); those ask for theirs, and so on down to the base cases. Each answer is written into the table on the way back up, and any call that finds its cell already filled returns immediately instead of recursing again. The table is not a plan here, it is a memory.

Its recurrence

F(i) = memo[i] ?? F(i−1) + F(i−2)

When it is the right choice

Top-down is the easier of the two to write, because it is the recursion you already had with three lines added, and it only ever computes the subproblems it actually needs — which matters when the table is large and sparse. Bottom-up avoids the call stack and is usually faster by a constant factor. On this table they do identical work, which is exactly why this pair is the place to compare them.

How it works

• Ask for the cell you want: F(n).
• If that cell is already filled, hand the value back without doing anything else.
• If it is a base case, fill it and hand it back.
• Otherwise ask for the two cells behind it, which suspends this call until both answer.
• Add the two answers, write the result into the cell, and hand it back.

Worth noticing

• The stack is the difference. The pseudocode panel shows every suspended call parked on the line it is waiting at, and the cells they are waiting on are marked in the table — a chain reaching down to the base cases, where the bottom-up page has a row filling left to right and nothing waiting at all.
• Watch the memo-hit counter. Every hit is a subtree of the naive recursion that did not happen, and on a table this small it is already most of the work.
• The table ends up identical to the bottom-up page’s, cell for cell. Race them and the counters agree at the end; only the order differs, and that order is the entire content of the words "top-down" and "bottom-up".
• Neither Fibonacci page has a traceback, and there is no traceback to have: the answer is a number in one cell rather than a path through the table. Every other page in this tool reads its answer out of the walk back instead, which is the contrast worth carrying to them.

Cost

Best

O(n)

Average

O(n)

Worst

O(n)

Extra space

O(n)

Table

one dimension

Accepts

n from 1 to 20

The limits are pedagogical rather than technical: this tool keeps the whole table in every recorded step, so the shape of the table sets the size of the trace directly, and a run has to stay short enough to sit and watch. An input that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the input sizes rather than by running it and finding out.

An unfilled cell is drawn differently from a cell holding a zero — no fill, a dashed outline, and no number at all — because early in a run that difference is most of the picture.

Worth comparing

• Fibonacci, bottom-up — The same table filled in the other direction, with no stack at all. Racing the two on one clock is the clearest thing in this module.
• 0/1 knapsack — Where top-down starts to pay: a two-dimensional table whose reachable cells are a fraction of the whole.
• Memoised Fibonacci as a call tree — The identical algorithm drawn as a call tree rather than as a table, with the repeated subtrees cut away. That tool shows what the recursion does; this one shows where the answers are kept.
• Fibonacci as a call tree — The same computation drawn as the recursion it is rather than as the table it fills. The naive call tree recomputes fib(3) five times over; this table computes it once, and the two pictures side by side are the shortest honest definition of dynamic programming there is.

All dynamic programming algorithms