Dynamic Programming
Dynamic Programming is a general algorithm design technique for solving problems defined by recurrences with overlapping subproblems.
- Invented by American mathematician Richard Bellman in the 1950s to solve optimization problems and later assimilated by CS.
- “Programming” here means “planning.”
- Main idea:
- Set up a recurrence relating a solution to a larger instance to solutions of some smaller instances.
- Solve smaller instances once.
- Record solutions in a table.
- Extract solution to the initial instance from that table.
Dynamic programming is a very powerful, general tool for solving optimization problems.
Once understood it is relatively easy to apply, but many people have trouble understanding it.