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 2: Why Fibonacci Explodes
Fib of n is fib of n minus one plus fib of n minus two. The base cases, fib of zero and fib of one, stop the calls.
Each call to fib of five splits into two smaller calls, and each of those splits again, until the calls reach zero or one.
Now look for repeats. Fib of three shows up twice, fib of two three times. Each copy redoes all its work from nothing.
Count the calls. Five takes fifteen, ten takes one seventy-seven, thirty takes over two and a half million. Each step multiplies the work.
Computing fib of thirty recurses into the same smaller calls over and over. It asks only thirty-one distinct questions, yet makes millions of calls. Most of the work is repeated.
The blowup comes from forgetting: only a few distinct answers exist, yet we recompute them endlessly. Next page, we fix that by remembering each answer the first time.