Dynamic programming

Dynamic programming applies when a problem is made of smaller problems that overlap. Recursion still describes the answer. The difference from backtracking is that you store results instead of exploring the same state twice.

Climbing stairs is the friendly introduction. You may take 1 or 2 steps. The number of ways to climb n steps is the ways to climb n − 1 plus the ways to climb n − 2, because the last action was one of those two. That sentence is the recurrence. The base cases are the small staircases you can count by hand: one way up a single step, two ways up two steps.

A naive recursion recomputes the same smaller staircases many times on the way to a larger n. Two repairs share the name. Memoisation caches each answer on the way down. A loop fills a table from the bottom, and if you only keep the last two numbers the extra memory is constant. Both are dynamic programming. The loop is usually what you write once you trust the recurrence. The same shape extends to grids and to coin change. If you can write the recurrence and the base case, the table is mechanical.