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 6: Fewest Coins, Step by Step
Coins of 1, 4 and 5 make eight. Grabbing the biggest first, 5 plus three 1s, takes four coins. Two 4s take only two.
Box a holds the fewest coins that make exactly a. Our answer will be box eight.
Pick a last coin c. Then you need one coin, plus the best answer for a minus c. Try each coin and keep the smallest total.
Put together: box a is one plus the minimum, over every coin c that fits, of box a minus c. Overlapping questions, best pieces. It fits.
Step three: the base case. Making zero takes zero coins. Put a zero in box zero. Everything else grows from that one starting value.
Step four: fill left to right. For each box, check every coin and keep the smallest result. Box eight: four, two, four. Smallest is two.
Same four moves every time: define the box, write its dependency, set the base case, fill in order. Fibonacci and coins share one recipe.
Dynamic programming is not a bag of tricks: it is four questions you can ask of any problem, and a table that answers them.