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.