## 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

(*c1*,*v1*) ←*best-cuts*(*j*)

(*c2*,*v2*) ←*best-cuts*(*i*-*j*)

*v′*←*v1*+*v2*

**if**(*v′*<*v*)

*v*←*v′*

*c*← (*c1*∪ {*j*} ∪ adjust(*c2*,*j*),*v′*)

**return**(*c*,*v*)

### 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

- Associativity matters: (10x100)
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?