Dynamic programming tutorial

Dynamic programming. The whole move: never solve the same problem twice.

Plain recursion repeats itself. F of five needs F of four and F of three, but F of three comes back below, and F of two shows up three times. Save each answer once, and every repeat becomes a lookup.

Or build up from the smallest case: fill a row of answers, each cell made once from the ones before it.

The clue: a problem asks for a count, a best, or a yes or no, and the answer for N depends on smaller sizes.

The cost: states times work per state. N states, constant work each, is linear time. Now let's use it on Climbing Stairs.