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 5: When the Trick Applies
Remembering answers works beautifully for Fibonacci, but only for problems with a particular shape. Two properties describe that shape.
First property: overlap. The same small questions keep showing up. In Fibonacci's call tree, the same fib values appear in several branches. Saving one answer pays off repeatedly.
Contrast: split a list in half and sort each half. Every piece is different, nothing repeats, so a memory table would sit empty. Overlap is what earns the table.
Second property: the best answer to the whole is built from best answers to the pieces. That's why a saved answer can be trusted and simply plugged in.
Think of a cheapest route from A to C through B. The A-to-B stretch must be the cheapest A-to-B, or swapping in a cheaper one would improve the whole.
Ask two questions: do the small subproblems repeat, and does the best answer to each piece build the best whole? If both are yes, a table of stored answers works.
Dynamic programming isn't a cure for slow recursion; it's a match between a trick and a shape. Spot recurring questions and best-from-best pieces, and you know the trick will work.