Lecture 17: Dynamic Programming Overview
Main idea of DP
STEP 1: Recursively define the value of an optimal
solution (difficult part)
Copyright By PowCoder代写 加微信 powcoder
STEP 2: Compute the value of an optimal solution from the smallest to the largest problems.
One Dimensional (1D) Dynamic Programming
• Solve problems of minimum size first.
• Store solutions in 1D array.
• Gradually increase problem size.
• Choose the order that you solve problems, so that you re-use solutions of smaller problems stored in the 1D array.
• How to gradually increase the problem size:
• If you need to select among a set of n items, order
items (sometimes in arbitrary order) and allow
selection among the first 1,2,…,n items.
• If you need to solve for an integer amount or length n,
gradually solve for 1,2, …,n
1D DP Simple Problems
1. Fibonacci Numbers
2. Maximum Sum problem
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.
: Given a sequence A of n positive
LetA bethesubsequenceofthefirstinumbers(i≤n):a,a ,…,a
Let W be the sum of numbers in the optimal solution for A . ii
Recurrence: W = max{W + a, W } i i-2 i i-1
max(a1, a2)
1D DP More Complex Problems
1. Problem : Given a rod of length and prices for ,where isthepriceofarodoflength ,cuttherod
in order to maximize the total revenue.
• is maximum revenue from cutting rod of length n
• Recurrence: ,
2. Minimum number of Coins : Given amount n and k denominations d1, … ,dk , find minimum number of coins for amount n
max(2p1, p2)
Let d be the last denomination used i
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
Recurrence: C[n] = 1 + min{C[n-d ]}, for d , … ,d i1k
1D DP More Complex Problems -2
1. Weighted interval scheduling .
Goal: find maximum-weight subset of mutually compatible jobs. Sort jobs by finishing time: .
• largest index such that job is compatible with job .
• value of optimal solution to the problem on jobs . • Recurrence: ,
Two jobs compatible if they don’t overlap.
Job starts at , finishes at , and has weight (or value) .
2. Similar problem- Highway Billboards
from west to east. You can place billboards at locations x1, x2, …, xn. If you place a billboard at xi, you receive revenue of ri>0. You wish to place billboards as to maximize your total revenue, subject to the restriction that any two billboards must be at least 5 miles apart.
Sort the sites in increasing order of location {x , x , …, x } 12n
Recurrence and algorithm same as Weighted interval scheduling.
: Consider a highway
Exercise on Longest Oscillating Subsequence A sequence of numbers is oscillating if
• for every odd index i and
• for every even index i Example:
Describe a DP algorithm to find a longest oscillating subsequence (LOS) in a sequence of n integers. Assume that all numbers are distinct. Successive numbers in LOS do not have to be immediate neighbors in the initial sequence.
Longest Oscillating Subsequence: Recurrence
: length of the longest oscillating subsequence that ends at and has an even length
: length of the longest oscillating subsequence that ends at and has an odd length
if is the last number before in subsequence (j
if is the last number before in subsequence (j
𝑠𝑖,𝑗 ←𝑘 Construct-RNA(𝑠, 1, 𝑛)
Construct-RNA(𝑠, 𝑖, 𝑗):
if 𝑖≥𝑗−4 then return
if 𝑠 𝑖, 𝑗 = 0 then Construct-RNA(𝑠, 𝑖, 𝑗 − 1) print 𝑠 𝑖,𝑗 ,”-”,𝑗
Construct-RNA(𝑠,𝑖,𝑠𝑖,𝑗 −1) Construct-RNA(𝑠,𝑠𝑖,𝑗 +1,𝑗−𝟏)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com