Chapter Objectives

Dynamic Programming

• Not a specific algorithm, but a technique (like divide-and-conquer).
• Developed back in the day when “programming” meant “tabular method” (like
  linear programming). Doesn’t really refer to computer programming.
• Used for optimization problems:
  • Find a solution with the optimal value.
  • Minimization or maximization. (We’ll see both.)

Four-step method
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution in a bottom-up fashion.
4. Construct an optimal solution from computed information.