# 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.r * m.c * m.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?