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 3: Remember What You Computed
Naive Fibonacci keeps asking the same questions. So keep a notebook: before computing anything, check whether you've already written the answer down.
Three moves: check the notebook for the answer; if it's there, return it. Otherwise compute it, write it in the notebook, then return it. Same recursion, plus memory.
Trace fib(5). The left chain computes everything once. Every right-hand branch that used to recurse is now a single notebook lookup, so the tree shrinks to a line.
Count it. Only n plus one distinct questions exist. Each is solved once, with constant work. Total work is linear in n, instead of exponential.
The lesson: count your distinct questions, and make sure you answer each only once. That single habit is the heart of dynamic programming.