CS代考 Lecture 14:

Lecture 14:
Introduction to Dynamic Programming

Dynamic Programming (DP)

Copyright By PowCoder代写 加微信 powcoder

• Similar to Greedy, DP is used for optimization problems, but it can find optimal solutions when Greedy fails
• Similar to Divide and Conquer (D&C), DP partitions a problem into subproblems
• D&C works recursively top-down
Solve some smaller problems that are combined for the larger problem
• DP is also based on a recursive problem definition, using problems of smaller size
Main idea of DP
Recursively define the value of an optimal solution using smaller problem sizes (also called optimal substructure – this is the difficult part)
• Once you have the recurrence, it is easy to write recursive pseudocode (top down approach). To avoid re-computing the same problems many times, you can use memoization. Store results, and if there is a subsequent call to a result that has been already computed, use the stored result instead of executing again.
• We use the non-recursive, bottom up approach: solve the smallest problems first, store the solutions, and use them to solve larger problems.

Fibonacci Numbers
Recursive algorithm with Memoization Non-recursive bottom up algorithm
Memoized – Top Down
Allocate array F[1..n]=[1,2,0,0,…] to store Fibonacci numbers already computed. Perform recursive call only for non-computed values.
if F[n]≠ 0 return F[n] F[n]← TD-F(𝑛−1)+TD-F(𝑛−2) return F[n]
Non- recursive – Bottom Up
No need for array because only last two numbers are useful
𝐹𝑝 ← 1; 𝐹 ← 2 for 𝑖=3 to 𝑛
𝑡𝑒𝑚𝑝 ← 𝐹𝑝;𝐹𝑝 ← 𝐹
𝐹 ← 𝐹𝑝 + 𝑡𝑒𝑚𝑝 return 𝐹
Both avoid solving a subproblem more than once by storing solutions. Bottom up is faster as it avoids recursive calls.
It also permits space optimization ( versus ) for top down. We will use bottom up dynamic programming in this class

Exercise on Maximum Sum problem
Recall the problem:
Let A be a sequence of n positive numbers a1, a2, . . , an.
Find a subset S of A that has the maximum sum, provided that if we select ai in S, then we cannot select ai-1 or ai+1.
Greedy solution: G = {8,3}
Optimal solution: O = {7,6}
Design a DP Algorithm that always finds the optimal solution.
For example, for A= 7, 8, 6, 3.
Greedy would select the largest number, delete the two neighbors and

DP for Maximum Sum
General idea:
Let Ai be the subsequence of A containing the first i numbers (i ≤ n): a1,
a2, . . . , ai
Let Si be the solution of problem Ai. Let Wi be the sum of numbers in Si.
Two possibilities for ai :
ai isinSi. => ai-1 isnotinSi, andWi =Wi-2+ai. ai isnotinSi. => ai-1 canbeinSi andWi =Wi-1.
Step 1: (Recurrence): Solution is larger of the two cases: Wi = max{Wi-2+ ai, Wi-1}.
Step 2: Solve the problem incrementally from smaller to larger, i.e. for A1, A2, …, An. The final solution is An.

DP pseudocode
W[1] = a1 ;b[1] = true // in general b[i] = true means that ai is in Si Ifa2 >a1
else W[2]=a2;b[2]=true//a2 isinS2
W[2]=a1; b[2]=false//a2 isnotinS2 for i =3 to n
If W[i−2] + ai > W[i−1] W[i] = W[i−2] + ai
b[i]=true//ai isinSi
W[i] = W[i−1]
b[i]=false//ai isnotinSi
Cost: (n)
Example: for A= 1, 8, 6, 3, 7, we have
W[1] = 1, b[1] = 1 W[2] = 8, b[2] = 1 W[3] = 8, b[3] = 0 W[4] = 11, b[4] = 1 W[5] = 15, b[5] = 1

while i > 0
Printing the solution
if b[i] is true Output ai
i = i−2 else
Example: for A= 1, 8, 6, 3, 7, we have b[5] = 1; therefore, we print a5=7 and set i=3 b[3] = 0; therefore, we set i=2
b[2] = 1; therefore, we print a2=8 and set i=0

Exercise on Minimum number of Coins Input: Amount n and k denominations d1, … ,dk
Output: Minimum number of coins for amount n
Greedy solution: Give as many coins as possible from the largest denomination, then from the from second largest, and so on.
Greedy solution is not optimal for arbitrary coin denominations
n = 30c, d1 = 25c, d2 = 10c, d3 = 1c Greedy solution: 6 (1×25+5X1) Optimal solution: 3 (3×10)

DP approach
We will find a formula that expresses the solution for amount n, as a recurrence of solutions for smaller amounts
This is the most crucial step
Then, we will start solving the small problems,
gradually increasing their size, until we reach n. We will keep all solutions in a table
The last solution in the table corresponds to the minimum number of coins for amount n
If want to remember which denominations were used, we need an additional table

Recurrence
Let C[n] be the minimum number of coins for amount n
Let di be the last denomination used
Step 1 Recurrence: C[n] = 1 + min{C[n-di]}, for d1, … ,dk Step 2: Solve the problem for amount 1,2…, n
Then: C[n] = 1 + C[n-d ] i
– Because after using 1 coin, the amount left is n-di But I have to consider all possible (k) denominations

DP-Coin(n)
C[< 0] = ∞; C[0] = 0 For p = 1 to n For i = 1 to k // initialization // for each amount (problem size) // for each denomination C[p] = min S[p] = coin Cost: (nk) min = C[p − di] + 1 // min number of coins for amount p // last coin used for amount p if (p ≥ di) if (1+C[p − di]) < min) // If amount is at least as large as the coin Printing the solution While n > 0
print S[n] // last coin used
n = n − S[n] // remaining amount

The Problem
Problem: Given a rod of length and prices 􏰌 for , where 􏰌 is the price of a rod of length . Find a way to cut the rod to maximize total revenue.
length 1 2 3 4 5 6 7 8 9 10 price 𝑖 1 5 8 9 10 17 17 20 24 30
Want to calculate the maximum revenue rn that can be achieved by cutting a rod of size n. Will do this by finding a way to calculate rn from r1, r2, …, rn-1
There are 2􏰀􏰓􏰆 ways of cutting rod of size n . Too many to check all of them separately.

Visualization of Optimal Substructure
2 3 Initial rod n-1 Choices
123 n-1 ………
•Cut a piece of length 1 •Find the optimal division for length n-1
•Cut a piece of length 2 •Find the optimal division for length n-2
•Cut a piece of length n-1 •Find the optimal division for length 1
123 n-1 123 n-1
Revenue p1+rn-1
Revenue p2+rn-2
Revenue pn-1+r1 =pn-1+p1
Revenue pn
Sell in one piece
The best choice is the maximum of p1+rn-1, p2+rn-2 , …, pn-1+r1, pn

: Another View
Define: Let 􏰀 be the maximum revenue obtainable from cutting a rod of length .
Step 1 Recurrence:
􏰀 􏰀 􏰆 􏰀􏰓􏰆 􏰈 􏰀􏰓􏰈 􏰀 ifwedonotcutatall
􏰆 􏰀􏰓􏰆 if the first piece has length
􏰈 􏰀􏰓􏰈 if the first piece has length
Step 2 Recurrence: Solve the problem for rod length 1,2,…,n.

: The Algorithm
Define: Let 􏰀 be the maximum revenue obtainable from cutting a rod of length .
Recurrence:
􏰀 􏰀 􏰆 􏰀􏰓􏰆 􏰈 􏰀􏰓􏰈 􏰀􏰓􏰆 􏰆 􏰆 􏰆
Running time:
let 𝑟[0 ..𝑛] be a new array 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
𝑞 ← max(𝑞, 𝑝[𝑖] + 𝑟[𝑗 − 𝑖]) max revenue if first piece has length ∈[1,𝑗]
𝑟𝑗←𝑞 return 𝑟[𝑛]
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30

: The Algorithm
Define: Let 􏰀 be the maximum revenue obtainable from cutting a rod of length .
Recurrence:
􏰀 􏰀 􏰆 􏰀􏰓􏰆 􏰈 􏰀􏰓􏰈 􏰀􏰓􏰆 􏰆 􏰆 􏰆
Running time:
let 𝑟[0 ..𝑛] be a new array 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
𝑞 ← max(𝑞, 𝑝[𝑖] + 𝑟[𝑗 − 𝑖]) max revenue if first piece has length ∈[1,𝑗]
𝑟𝑗←𝑞 return 𝑟[𝑛]
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30

: The Algorithm
Define: Let 􏰀 be the maximum revenue obtainable from cutting a rod of length .
Recurrence:
􏰀 􏰀 􏰆 􏰀􏰓􏰆 􏰈 􏰀􏰓􏰈 􏰀􏰓􏰆 􏰆 􏰆 􏰆
Running time:
let 𝑟[0 ..𝑛] be a new array 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
𝑞 ← max(𝑞, 𝑝[𝑖] + 𝑟[𝑗 − 𝑖]) max revenue if first piece has length ∈[1,𝑗]
𝑟𝑗←𝑞 return 𝑟[𝑛]
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30
􏰆􏰈􏰈􏰆􏰏􏰇= =8

: The Algorithm
Define: Let 􏰀 be the maximum revenue obtainable from cutting a rod of length .
Recurrence:
􏰀 􏰀 􏰆 􏰀􏰓􏰆 􏰈 􏰀􏰓􏰈 􏰀􏰓􏰆 􏰆 􏰆 􏰆
Running time:
let 𝑟[0 ..𝑛] be a new array 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
𝑞 ← max(𝑞, 𝑝[𝑖] + 𝑟[𝑗 − 𝑖]) max revenue if first piece has length ∈[1,𝑗]
𝑟𝑗←𝑞 return 𝑟[𝑛]
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30
0 1 5 8 10
􏰆 􏰏􏰈 􏰈􏰏 􏰆􏰚 􏰇= =10

: The Algorithm
Define: Let 􏰀 be the maximum revenue obtainable from cutting a rod of length .
Recurrence:
􏰀 􏰀 􏰆 􏰀􏰓􏰆 􏰈 􏰀􏰓􏰈
let 𝑟[0 ..𝑛] be a new array 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
𝑞 ← max(𝑞, 𝑝[𝑖] + 𝑟[𝑗 − 𝑖]) max revenue if first piece has length ∈[1,𝑗]
𝑟𝑗←𝑞 return 𝑟[𝑛]
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30
0 1 5 8 10 13 17 18 22 25 30
Running time:
This only finds max-revenue.
How can we construct SOLUTION that yields max-revenue

Reconstructing the Solution
Idea: Remember the optimal decision for each subproblem in
let 𝑟[0 ..𝑛] and 𝑠[0 ..𝑛] be new arrays 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
if 𝑞 < 𝑝[𝑖] + 𝑟[𝑗 − 𝑖] then 𝑞 ← 𝑝[𝑖]+𝑟[𝑗 − 𝑖] while 𝑗>0 do print 𝑠[𝑗]
𝑗 ← 𝑗 − 𝑠[𝑗]
but keeps track in s[j]
to previous alg
of where max occurred
0 1 2 3 4 5 6 7 8 9 10 0 1 5 8 9 10 17 17 20 24 30 0

Reconstructing the Solution
Idea: Remember the optimal decision for each subproblem in
let 𝑟[0 ..𝑛] and 𝑠[0 ..𝑛] be new arrays 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
if 𝑞 < 𝑝[𝑖] + 𝑟[𝑗 − 𝑖] then 𝑞 ← 𝑝[𝑖]+𝑟[𝑗 − 𝑖] while 𝑗>0 do print 𝑠[𝑗]
𝑗 ← 𝑗 − 𝑠[𝑗]
but keeps track in s[j]
to previous alg
of where max occurred
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30 01

Reconstructing the Solution
Idea: Remember the optimal decision for each subproblem in
let 𝑟[0 ..𝑛] and 𝑠[0 ..𝑛] be new arrays 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
if 𝑞 < 𝑝[𝑖] + 𝑟[𝑗 − 𝑖] then 𝑞 ← 𝑝[𝑖]+𝑟[𝑗 − 𝑖] while 𝑗>0 do print 𝑠[𝑗]
𝑗 ← 𝑗 − 𝑠[𝑗]
but keeps track in s[j]
to previous alg
of where max occurred
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30 015

Reconstructing the Solution
Idea: Remember the optimal decision for each subproblem in
let 𝑟[0 ..𝑛] and 𝑠[0 ..𝑛] be new arrays 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
if 𝑞 < 𝑝[𝑖] + 𝑟[𝑗 − 𝑖] then 𝑞 ← 𝑝[𝑖]+𝑟[𝑗 − 𝑖] while 𝑗>0 do print 𝑠[𝑗]
𝑗 ← 𝑗 − 𝑠[𝑗]
but keeps track in s[j]
to previous alg
of where max occurred
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30 0158

Reconstructing the Solution
Idea: Remember the optimal decision for each subproblem in
let 𝑟[0 ..𝑛] and 𝑠[0 ..𝑛] be new arrays 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
if 𝑞 < 𝑝[𝑖] + 𝑟[𝑗 − 𝑖] then 𝑞 ← 𝑝[𝑖]+𝑟[𝑗 − 𝑖] while 𝑗>0 do print 𝑠[𝑗]
𝑗 ← 𝑗 − 𝑠[𝑗]
but keeps track in s[j]
to previous alg
of where max occurred
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30 0 1 5 8 10

Reconstructing the Solution
Idea: Remember the optimal decision for each subproblem in
let 𝑟[0 ..𝑛] and 𝑠[0 ..𝑛] be new arrays 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
if 𝑞 < 𝑝[𝑖] + 𝑟[𝑗 − 𝑖] then 𝑞 ← 𝑝[𝑖]+𝑟[𝑗 − 𝑖] while 𝑗>0 do print 𝑠[𝑗]
𝑗 ← 𝑗 − 𝑠[𝑗]
but keeps track in s[j]
to previous alg
of where max occurred
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30
0 1 5 8 10 13 17 18 22 25 30 0 1 2 3 2 2 6 1 2 3 10

Reconstructing the Solution
Idea: Remember the optimal decision for each subproblem in
Reconstructing solution for n =9 j=9 s[j] = 3
j=9-3 =6 s[j] = 6
Solution is to cut 9 into {3, 6}
let 𝑟[0 ..𝑛] and 𝑠[0 ..𝑛] be new 𝑟0←0
for 𝑗←1 to 𝑛
for 𝑖←1 to 𝑗
if 𝑞<𝑝[𝑖]+𝑟[𝑗−𝑖] then 𝑞 ← 𝑝[𝑖] + 𝑟[𝑗 − 𝑖] while 𝑗>0 do
print 𝑠[𝑗] 𝑗←𝑗−𝑠[𝑗]
pull off first piece & construct opt soln
of remainder
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30
0 1 5 8 10 13 17 18 22 25 30 0 1 2 3 2 2 6 1 2 3 10

Weighted Interval Scheduling
Weighted interval scheduling problem.
Job starts at 􏰙 , finishes at 􏰙 , and has weight (or value) 􏰙 .
 Two jobs compatible if they don’t overlap.
 Goal: find maximum-weight subset of mutually compatible jobs.
a (3) b (1)
0 1 2 3 4 5 6 7 8 9 10 11

Weighted Interval Scheduling
Weighted interval scheduling problem.
Job starts at 􏰙 , finishes at 􏰙 , and has weight (or value) 􏰙 .
 Two jobs compatible if they don’t overlap.
 Goal: find maximum-weight subset of mutually compatible jobs.
a (3) b (1)
Solution is {d,h} With value 18
0 1 2 3 4 5 6 7 8 9 10 11

Unweighted Interval Scheduling Review
Recall. Greedy algorithm works if all weights are 1.
 Consider jobs in ascending order of finish time.
 Add job to subset if it is compatible with previously chosen jobs.
Observation. Greedy algorithm can fail miserably if arbitrary weights are allowed.
weight = 999 weight = 1
0 1 2 3 4 5 6 7 8 9 10 11

Weighted Interval Scheduling
Notation. Label jobs by finishing time: 􏰆 􏰈 􏰀.
largest index
Note: all jobs ’ with
1 𝑝(1) = 0
2 𝑝(2) = 0 3 𝑝(3) = 0
4 𝑝(4) = 1 5 𝑝(5) = 0
6 𝑝(6) = 2
7 𝑝(7) = 3
8 𝑝(8) = 5
0 1 2 3 4 5 6 7 8 9 10 11
such that job is compatible with job .
are not compatible with j
Q: How to compute ?
A: Sort jobs by finish time, and then do binary search with 􏰙 in
time to find largest comp

The Recurrence
Def. value of optimal solution to the problem on jobs . Step 1 Recurrence: Solve the problem for jobs {1}, {1,2}, …, {1,2,…,n}.
Case 1: Select job .
– can’t use incompatible jobs
– must include optimal solution to problem on jobs
Case 2: Do not select job .
– must include optimal solution to problem on jobs
Step 2: Solve the problem by incrementally including jobd 1,2,…,n.
sort all jobs by finish time
for 𝑗←1 to 𝑛
𝑉 𝑗 ← max{𝑣𝑗 + 𝑉[𝑝(𝑗)], 𝑉[𝑗 − 1]} return 𝑉[𝑛]

The Complete Algorithm
sort all jobs by finish time
for 𝑗←1 to 𝑛
if 𝑣𝑗+𝑉𝑝𝑗 >𝑉[𝑗−1] then Job j in opt soln
𝑉𝑗 ←𝑣𝑗+𝑉𝑝𝑗
for jobs [1..j]
Job j NOT in opt
soln for jobs [1..j
If j in final soln
then remainder (to
left) of soln is
opt soln for [1..p[j]]
𝑉𝑗 ←𝑉𝑗−1 𝑘𝑒𝑒𝑝 𝑗 ← 0
while 𝑗>0 do
if 𝑘𝑒𝑒𝑝𝑗 =1 then
print 𝑗 𝑗 ← 𝑝(𝑗)
Running time:
Alg on previous page only found optimal value of solution.
To find actual solution, we need to keep track of which jobs are kept in solution

The Recurrences
1. Fibonacci Numbers
􏰀 is maximum revenue from cutting rod of length n 􏰀 􏰆􏰜􏰌􏰜􏰀 􏰌 􏰀􏰓􏰌, 􏰇
3. Weighted Interval Scheduling
is maximum-weight subset of mutually compatible jobs on jobs .
2. The Problem

Exercise on Highway Billboards
Consider a highway from west to east. The possible sites for billboards are given by numbers x1, x2, …, xn, each in the interval [0, M]. If you place a billboard at location xi, you receive revenue of ri>0.
Regulations imposed by the county’s Highway Department require that every two of the billboards must be at least 5 miles apart.
You wish to place billboards at a subset of sites so as to maximize your total revenue, subject to this restriction.
Q1: Describe a greedy algorithm for the problem
A1: Problem and greedy algorithm is similar to the max sum problem.
(i) Place the first billboard at the site xi with the maximum revenue, (ii) remove xi and all sites within 5 miles from xi , and (iii) repeat until not site is left.
Q2: Does the above greedy algorithm always find the optimal solution?
A2: No. For the same reason that the greedy algorithm does not give optimal solution for the max sum problem. You can create counter-examples, by taking suboptimal solutions for the max sum problem, and consider that (i) the numbers in the max sum correspond to revenues of sites, and (ii) the distance between neighboring sites is 4 miles (so if you select a site you cannot select the previous and the next one).

DP for Highway Billboards
Q: Describe the recurrence for dynamic programming
Solution is similar to Weighted Interval Scheduling
Sort the sites in increasing order of location {x1, x2, …, xn}
Let p(i) be the largest j5, i.e., xj is the last site before that is compatible with xi.
Define R(i) be the revenue of the optimal solution for the first i sites. For computing R(i), I have 2 options:
1. If I do not use site xi, the revenue is R(i-1).
2. If I use site xi, the revenue is ri+ R(p(i)).
Thus, R(i) =max {R(i-1), ri+ R(p(i))}, R(0)=0;
Algorithm: Solve the problem for increasing number of sites – i.e., step i, solves the problem for the first i sites in the sorted order.