4.6 Dynamic Programming

R. Bellman began the systematic study of dynamic programming in 1955. The word ``programming'', both here and in linear programming, refers to the use of a tabular solution method. Although optimization techniques incorporating elements of dynamic programming were known earlier, Bellman provided the area with a solid mathematical basis. Dynamic programming typically applies to optimization problems in which a set of choices must be made in order to arrive at an optimal solution. As choices are made, subproblems of the same form often arise. Dynamic programming is effective when a given subproblem may arise from more than one partial set of choices; the key technique is to store, or ``memorize'', the solution to each such subproblem in case it should reappear. The development of a dynamic-programming algorithm can be broken into a sequence of four steps:

1. Characterize the structure of an optimal solution

2. Recursively define the value of an optimal solution

3. Compute the value of an optimal solution in a bottom-up fashion

4. Construct an optimal solution from the value(s) of the optimal solution.

Steps 1-3 (Forward) form the basis of a dynamic-programming solution to a problem. Step 4 (Traceback) can be omitted if only the value of an optimal solution is required. When we do perform step 4, we sometimes maintain additional information during the computation in step 3 to ease the construction of an optimal solution.

The key ingredients that an optimization problem must have for dynamic programming to be applicable are: optimal substructure and overlapping subproblems.

Optimal substructure:

The first step in solving an optimization problem by dynamic programming is to characterize the structure of an optimal solution. We say that a problem exhibits optimal substructure if an optimal solution contains optimal solutions to its subproblems.

Overlapping subproblems:

The second ingredient is that the space of subproblems must be ''small'' in the sense that a recursive algorithm for the problem solves the same subproblems over and over, rather than always generating new subproblems. Typically, the total number of distinct subproblems is a polynomial in the input size. When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has overlapping subproblems.