Dynamic Programming

Never solve the same problem twice

An interactive lesson with 7 steps, about 6 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Dynamic programming stores answers to subproblems instead of recomputing them.
• Build a table from small cases up, using a recurrence.
• It finds optimal answers where greedy choices fail.

Steps

1. Remember answers
2. With a table
3. Making change, properly
4. Where greedy fails
5. Ten cents
6. Where else?
7. Climbing stairs