Example DP1: Dynamic Programming Example

The general idea behind dynamic programming is to iteratively find the optimal solution to a small part of the whole problem.  Using the previous solution, enlarge the problem slightly and find the new optimum solution. Continue enlarging until you have solved the whole problem, then trace back to find the solution.

The characteristics of a problem that can be solved using dynamic programming are the following:
  • problem can be divided into stages
  • each stage has one or more states
  • you make a decision at each stage
  • the decision you make affects the state for the next stage
  • there is a recursive relationship between the value of the decision at the stage and the previously found optima

Example: The number of students that fail ENG101 depends on the number of TAs assigned to each section.  There are six TA available to be assigned to the course and there are four sections.  How many TAs should be assigned to each section of the course to have the fewest students fail?

The first step is to formulate the solution:

Press the Start button twice to begin the example.