Example 1: Dynamic Programming Example

The general idea behind dynamic programming is to 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 depend 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 least students fail?

The first step is to formulate the solution:

Press the Start button to begin the example.

This animation was made using Alligator Flash Designer 7.  More information about this program is available at Selteco Alligator.
You can view the source code for this animation using the trial verson of Alligator Flash Designer 7 and