DP1

Dynamic Programming Example

Dynamic Programming is iterative.  Each major step finds the optimal solution to a subproblem (a small part of the whole problem).  We then enlarge the subproblem slightly and use the optimum solutions found in the previous steps to find the optimum solution to the current subproblem. We continue enlarging subproblems until we have solved the entire problem, then trace back to find the solution.

Problems that can be solved by Dynamic Programming have these characteristics:

• 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 TAs 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. We use reverse recursion.

• stages: ENG101 sections (ie.  1st solve section D, 2nd solve sections C and D, 3rd solve sections B, C and D, 4th solve sections A, B, C and D)
• state at a stage: number of TAs available to be assigned
• decision: how many TAs to assign to section i
• decision update to state: number of available TAs to assign is reduced according to the decision.
• recursive value relationship:
• xᵢ : number of TAs assigned to section i
• Nᵢ(xᵢ) : number of students who fail ENG101 in section i given xᵢ TAs are assigned
• dᵢ : state (number of TAs available at the start of stage i)
• fᵢ(dᵢ) : best possible solution from stage i to the end

                    fᵢ(dᵢ) = min over x_i of {N_i(x_i) + f_i+1(d_i - x_i)}

Notice how the recursive relationship ties together (1) the local value of a decision at the current stage N_i(x_i) , and (2) the optimum solution for an already-solved subproblem  f_i+1(d_i - x_i). This use of previously-found optima is what makes dynamic programming efficient.