Overview

  • Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems.
  • Typically apply dynamic programming to optimization problems.
  • When developing a dynamic-programming algorithms, we follow a sequence of four steps:
    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, typically in a bottom-up fashion.
    4. Construct an optimal solution from computed information
  • Optimal substructure – optimal solutions to a problem incorporate optimal solutions to related subproblems, which we may solve independently.
  • Dynamic programming uses additional memory to save computation time; it servers an example of a time-memory trade-off.
  • There are usually two equivalent ways to implement a dynamic-programming approach:
    • Top-down with memoization
      • In this approach, we write each subproblem (usually in an array or hash table). The procedure now first checks to see whether it has previously solved this subproblem. If so, it returns the saved value, saving further computation at this level; if not, the procedure computes the value in the usual manner. We say that the recursive procedure has been memoized; it “remembers” what results it has computed previously.
    • Bottom-up method
      • This approach typically depends on some natural notion of “size” of a subproblem, such that solving any particular subproblem depends only on solving “smaller” subproblems. We sort the subproblems by size and solve them in size order, smallest first. When solving a particular subproblem, we have already solved all the smaller subproblems its solution depends upon, and we have saved their solutions. We solve each subproblem only once, and when we first see it, we have already solved all of its prerequisite subproblems.

Reconstructing a solution

  • Dynamic-programming approach can be extended to return not only the optimal value computed for each subproblem, but also a choice that lead to the optimal value.
  • Often involves using additional space to store selection.

Sample Problems

  • Rod cutting
    • Given a length n, and array p of prices, determine the maximum revenue obtainable by cutting up the rod and selling the pieces.
    • We say that the rod-cutting problem exhibits optimal substructure
  • Make change using the fewest possible coins

Resources

  • CLRS – Chapter 15 – Dynamic Programming
  • https://www.youtube.com/embed/8LusJS5-AGo