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?