Dynamic Programming

Memoization and Dynamic Programming

Bart Massey


Motivation For M&DP

  • In CS 350 you learned about:

    • Greedy algorithms: Fast, but usually no good
    • Recursive algorithms: General, but often not tractable
    • M&DP, but:
      • you may have forgotten
      • not in much depth
  • M&DP are techniques for getting tractable recursive algorithms

    • Applicable to many recursive problems
    • Trade tractable performance for tractable memory use
    • Idea: quit solving the same subproblem over and over
  • Plan for today:

    • Review M&DP
    • Look at the book problems
    • Discuss the homework problem

Example: Rod Cutting

  • Manufacturing problem: You have a rod of length n and want to cut it into rods of length i to maximize the sum of rod prices: rod price function p(i): N -> N

    • Example:

         (length, price, price density):
             (1, 1, 1.0), (2, 5, 2.5), (3, 8, 2.6{6}), (4, 9, 2.25),
             (5, 10, 2.0), (6, 17, 2.83{3}), (7, 17, 2.{428571}),
             (8, 20, 2.5), (9, 24, 2.6{6}), (10, 30, 3.0)
      
    • Greedy solution, n=4: 3 + 1 = 9

    • Better solution, n=4: 2 + 2 = 10

  • How do we find the "better solution" for arbitrary n and p?

Rod Cutting: Subproblems Compose

  • Basic idea: try one cut in the rod at various places and solve resulting subproblems; pick the smallest sum

    • Must work: if there is someplace the rod is cut, then hitting it will result in an optimal solution
    • Can solve recursively (top-down)
    • Don't need both recursions: cleaner and easier
    • Can return cuts as well as price

      best-cuts(i):
          if i ≤ 1
              return (∅, p(i))
          v ← p(i)
          c ← ∅
          for j ← 1 .. n - 1
              (c1v1) ← best-cuts(j)
              (c2v2) ← best-cuts(i - j)
              v′ ← v1 + v2
              if (v′ < v)
                  v ← v′
                  c ← (c1 ∪ {j} ∪ adjust(c2j), v′)
          return (cv)

Rod Cutting: Memoization

  • The recursive solution is correct, but slow. How slow?

    • Makes n recursive calls, where n is the length being cut
    • T[n] = 1 + sum(j=0..n-1, T[j]) = 2^n
    • Explores all unique cutting paths, so binary tree of depth n-1
  • Idea: Instead of re-calculating each T[i], remember it

       for i <- 0 .. n
           a[i] <- -1
       cut_price(i):
           if a[i] >= 0
               return a[i]
           if i <= 1
               return p(i)
           v <- p(i)
           for j <- 1 .. min(i - 1, 10)
               v' <- p(j) + cut_price(i - j)
               if (v' < v)
                   v <- v'
           a[i] <- v
           return v
    

Rod Cutting: Bottom-Up

  • Can solve iteratively (bottom-up)

     for i <- 1 .. n
         v[i] <- p(i)
         for j <- 1 .. i - 1
             v' <- v[j] + v[i - j]
             if (v' < v[i])
                 v[i] <- v'
    
  • No recursion cost (NBD?)

  • Might be cheaper lookup cost

  • Might calculate and store un-needed values

Matrix-Chain Multiplication

  • Cost of multiplying MxN by NxP matrix = MNP

  • For a chain of matrixes (MxN)(NxP)(PxQ)(QxR) ...

    • Associativity matters: (10x100)(100x5)(5x50) = 7500 vs 75000
    • Greedy is eliminate big indices first, doesn't work
  • M&DP is same pattern as before. Try to find a breakpoint:

    opt-cost(m[0..n-1]):
        v <- m[0].r * m[0].c * m[1].r + opt-cost(m[1..n-1])
        for i <- 2 .. n - 1
            v' <- opt-cost(m[1..i]) +
                  m[i].r * m[i].c * m[i+1].r +
                  opt-cost(m[i+1..n-1])
            if v' < v
                v <- v'
        return v
    
    • Memoize or bottom-up

More Problems

  • Longest Common Subsequence

  • Minimum Binary Search Tree

  • Minimum Edit Distance (exercise)

Homework Problem: Rod Joining

  • Dual of Rod Cutting: Want to purchase cheapest collection of rods for a given length n

  • Given table is boring, since unit rods are cheapest:

    • Add "join cost" of 2, i.e. cost 2(m - 1) for m-rod solution
  • Can solve by dynamic programming, for the same reason as rod cutting

  • Interesting corollary: How do rods end up priced given an efficient market?

Last modified: Tuesday, 29 April 2014, 9:54 AM