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?
