Selected Dynamic Programming(DP) Applications

SELETED DP APPLICATIONS

This section presents four applications, each with a new idea in the implementation of dynamic programming. As you study each application, pay special attention to the three basic elements of the DP model:

1.     Definition of the stages

2.     Definition of the alternatives at each stage

3.     Definition of the states for each stage

Of the three elements, the definition of the state is usually the most subtle. The applications presented here show that the definition of the state varies depending on the situation being modeled. Nevertheless, as you investigate each application, you will find it helpful to consider the following questions:

1.     What relationships bind the stages together?

2.     What information is needed to make feasible decisions at the current stage with-out reexamining the decisions made at previous stages?

My teaching experience indicates that understanding the concept of the state can be enhanced by questioning the validity of the way it is defined in the book. Try a dif-ferent definition that may appear "more logical" to you, and use it in the recursive computations. You will eventually discover that the definitions presented here provide the correct way for solving the problem. Meanwhile, the proposed mental process should enhance your understanding of the concept of the state.