Common Characteristics

There are a number of characteristics that are common to these two problems and to all dynamic programming problems. These are:

1. The problem can be divided into stages with a decision required at each stage.

   In the capital budgeting problem the stages were the allocations to a single plant. The decision was how much to spend. In the shortest path problem, they were defined by the structure of the graph. The decision was were to go next.

2. Each stage has a number of states associated with it.

   The states for the capital budgeting problem corresponded to the amount spent at that point in time. The states for the shortest path problem was the node reached.

3. The decision at one stage transforms one state into a state in the next stage.

   The decision of how much to spend gave a total amount spent for the next stage. The decision of where to go next defined where you arrived in the next stage.

4. Given the current state, the optimal decision for each of the remaining states does not depend on the previous states or decisions.

   In the budgeting problem, it is not necessary to know how the money was spent in previous stages, only how much was spent. In the path problem, it was not necessary to know how you got to a node, only that you did.

5. There exists a recursive relationship that identifies the optimal decision for stage j, given that stage j+1 has already been solved.
6. The final stage must be solvable by itself.

The last two properties are tied up in the recursive relationships given above.

The big skill in dynamic programming, and the art involved, is to take a problem and determine stages and states so that all of the above hold. If you can, then the recursive relationship makes finding the values relatively easy. Because of the difficulty in identifying stages and states, we will do a fair number of examples.