Dynamic Programming

What is dynamic programming?

Dynamic programming algorithms solve problems by combining the results of subproblems—just like divide-and-conquer algorithms. The following quote—attributed to George Santayana—rings true when thinking about how dynamic programming works:

Those who cannot remember the past are condemned to repeat it.

Characteristics

• Overlapping subproblems: The subproblems of a given problem are not independent. In other words, two subproblems share a problem.

• Optimal substructure property: The overall optimal solution of the problem can be constructed from the optimal solutions of its subproblems.

Dynamic programming patterns

There are two approaches that come in handy when a problem is to be solved using dynamic programming:

Memoization (top-down)

The memoized version of a problem is similar to the regular recursive version, except that it looks for the answer to a subproblem in a lookup table before computing its solution.