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
previous solution, enlarge the problem slightly and find the new
optimum solution. Continue enlarging until you have solved
whole problem, then trace back to find the solution.
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
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?
first step is to formulate the solution:
ENG101 sections (ie. 1st: section D, 2nd: section C and D,
3rd: section B, C and D, 4th: section A, B, C and D)
at a stage: number of TAs available to be
how many TAs to assign to section i
update to state: number of available TAs to
assign is reduced according to the decision.
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
You can view the source code for this animation using the trial verson
of Alligator Flash Designer 7 and