Nib asked, and Nib — askNib's tutor — drew the answer live at a whiteboard. This is the spoken transcript; enable JavaScript to watch it drawn.
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
Memoization starts at the top and digs down. But fib of n only ever needs the two smaller values. That means we already know the order.
Draw a row of boxes, zero through six. Fill the base cases first: zero in box zero, one in box one. No dependencies.
Loop left to right. Box two holds one plus zero, which is one. Box three holds one plus one, which is two. Each box is the sum of the two before it.
Same result, same linear work as memoizing. The difference is direction. Memoization recurses down from the question. Tabulation loops up from the base cases.
The one rule is order. Before filling any box, everything it depends on must already be filled. Smallest cases first, then build upward.
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.