What is dynamic programming, really? (for a curious adult who has seen a little code but never studied algorithms). Cover, in this order: What does it mean for a function to call itself?; Why does the obvious Fibonacci recursion explode?; What if you remember each answer the first time?; Can you skip the recursion and fill in a table instead?; What makes a problem fit this trick?; How do you use it on a brand-new problem, like fewest coins? — page 4: Filling In a Table

Nib asked for

Filling In a Table

the short answer

Instead of recursing down and remembering, you can start from the smallest case and fill a table upward, since each answer needs only entries already filled.

5 steps, drawn by Nib. Read it here, or watch him draw it. Updated 16 Oct 2026.

1the chain

On the last page, memoized Fibonacci started at the big question, fib(6), and recursed downward, caching answers as it returned. Notice something about that cache: fib(n) only ever needed fib(n-1) and fib(n-2), both smaller. So the order of work is knowable in advance, and nothing forces us to start from the top.

Each answer depends only on smaller ones, so the order is predictable.

a common mix-upDynamic programming requires recursion.

2the table

So flip it. Make a row of boxes labeled 0 through 6, one per subproblem. Fill in the base cases first: box 0 holds 0, box 1 holds 1. These need no other boxes, so they are the foundation everything else rests on.

Start by writing the base cases into the table.

3fill upward

Now sweep left to right with an ordinary loop. Box 2 is box 1 plus box 0, which is 1. Box 3 is box 2 plus box 1, which is 2. Each box is computed once, and when you reach it, the two boxes it needs are already filled. The answer to the original question is simply the last box.

Loop upward; every box finds its inputs already filled.

check yourself

What value goes in box 4, if boxes 2 and 3 hold 1 and 2?

Show the answer

3, since box 4 is box 3 plus box 2.

4two directions

Compare this with memoization. Both solve each subproblem exactly once, so both do linear work. The difference is direction: memoization goes top-down, discovering needed subproblems by recursing; tabulation goes bottom-up, solving every subproblem in a chosen order with a plain loop. No function calls pile up, which is why tabulation is often preferred in practice.

Same work, opposite direction: top-down versus bottom-up.

a common mix-upTabulation is a fundamentally different algorithm from memoization; it is the same subproblems and same recurrence, just ordered differently.

5the one rule

The key skill is choosing the fill order. It must guarantee that whenever you compute a box, everything it depends on is already done. For Fibonacci, left to right works. For other problems the order might differ, but the rule is the same: smallest cases first, building up.

Pick an order where every box's inputs come before it.

check yourself

Why can't we fill box 6 first in the table approach?

Show the answer

It needs boxes 5 and 4, which would not be filled yet.

Tabulation is memoization turned upside down: know the order, fill a table from the smallest case, and the answer is waiting in the last box.