Lecture 16: Dynamic Programming over Intervals
DP Over Intervals
Main idea of interval dynamic programming.
Copyright By PowCoder代写 加微信 powcoder
Problem contains items 1,2,…n. Recurrence gives optimal solution of the
original problem[1,n] as function of optimal solution of subproblems of
smaller length (length refers to the number of items in the problem)
• Base case contains problems of length 1, i.e., problem[1,1], problem [2,2],…,
problem [n,n].
• All solutions are stored in diagonals of a 2D array. Solutions of small
problems are re-used by bigger ones.
• Then, we solve n-1 problems of length 2, i.e., problem[1,2], problem[2,3],…, problem[n-1,n].
• Then, we solve n-l+1 problems of length l, i.e., problem[1, l], problem[2,l
+1],…, problem [n-l+1,n]
• Finally, we solve 1 problem of size n: problem [1,n]
Algorithm fills diagonals in a 2D table from smallest to largest problem length. First the main diagonal (base case), then the one on top of that,….At the end, the solution of the problem[1,n] is at the top right cell.
Longest Palindromic Substring
Def: A palindrome is a string that reads the same backward or forward.
radar, level, racecar, madam
“A man, a plan, a canal – Panama!” (ignoring space, punctuation, etc.)
Problem: Given a string , find the longest palindromic substring.
Palindromic substrings: CC, ACCA, ABA Longest palindromic substring: ACCA
Brute-force algorithm takes time. Recall: A substring must be contiguous
Dynamic Programming Solution
Def: Let be iff is a palindrome. The Recurrence:
Initial Conditions (subproblems of sizes 1 & 2)
– ACBBCABA
– ACBBCABA
The Actual Recurrence
if𝒊 𝒋AND – ACBBCABA
– ACBBCABA
A Completed DP Table
Initial Condition j=i; j=i+1
Largest is BCCCB
Running time:
Space: but can be improved to
The Algorithm
for 𝑖←1 to 𝑛−1 do
𝑝[𝑖,𝑖]←𝑡𝑟𝑢𝑒
if 𝑥𝑖 = 𝑥 then
𝑝𝑖,𝑖+1 ←𝑡𝑟𝑢𝑒, 𝑚𝑎𝑥←2 else 𝑝[𝑖,𝑖+1]←𝑓𝑎𝑙𝑠𝑒
for 𝑙←3 to 𝑛 do
for 𝑖←1 to 𝑛−𝑙+1 do
if 𝑝 𝑖+1,𝑗−1 =𝑡𝑟𝑢𝑒 and 𝑥 =𝑥 then
𝑝𝑖,𝑗 ←𝑡𝑟𝑢𝑒, 𝑚𝑎𝑥←𝑙 else 𝑝[𝑖,𝑗]←𝑓𝑎𝑙𝑠𝑒
return 𝑚𝑎𝑥
initial conditions
length 1 length 2
for each length 3 to n
starting character
ending character
Binary search trees (BST)
Tree-Search(𝑇, 𝑘):
𝑥 ← 𝑇. 𝑟𝑜𝑜𝑡
while 𝑥≠𝑛𝑖𝑙 and 𝑘≠𝑥.𝑘𝑒𝑦 do
if 𝑘<𝑥.𝑘𝑒𝑦 then 𝑥←𝑥.𝑙𝑒𝑓𝑡
else 𝑥←𝑥.𝑟𝑖𝑔h𝑡 return 𝑥
The (worst-case) search time in a balanced BST is
Q: If we know the probability of each key being searched for, can we design a (possibly unbalanced) BST to optimize the expected search time?
Similar Problem seen in : Binary Merge Tree
You are given a set of leaf nodes 𝑎, ... , 𝑎 and associated leaf weights 𝑤(𝑎),...,𝑤(𝑎)
Create a binary tree from the leaf nodes towards the root, in which the size of each node is the sum of the sizes of the two children.
A binary merge tree is optimal if it minimizes the weighted external path length. The weighted external path length of the tree is 𝐵 𝑇 = ∑ 𝑤 𝑎 𝑑(𝑎)
Cost = 30*2 + 20*2 + 10*1 = 110
Cost = 30*1 + 20*2 + 10*2 = 90
Merge L1 and L2, then with L3 Merge L2 and L3, then with L1
Optimal Binary Merge Tree Greedy Algorithm - Same as Input: n 2 leaf nodes, each with a size (i.e., # list elements) .
Output: a binary tree with the given leaf nodes which has a minimum total weighted external path lengths
Algorithm:
Create a min-heap T[1..n ] based on the n initial sizes. While (the heap size 2) do
extract from the heap two smallest values a and b
create intermediate node of size a + b whose children are a
insert the value (a + b) into the heap
Time complexity O(nlogn)
It can be shown that the Binary Merge Tree is optimal
The Optimal Binary Search Tree Problem
Problem Definition (simpler than the version in textbook):
Given keys binary search tree
is minimized, where
, with weights
, find a
keys such that
is the depth of .
Note: Similar to the Binary Merge Tree problem but with 2 key differences:
The tree has to be a BST, i.e., the keys are stored in sorted order.
In a Binary Merge Tree, there is no ordering among the leaves.
Keys appear as both internal and leaf nodes. In a Binary Merge Tree,
keys (characters) appear only at the leaf nodes.
Motivation: If the weights are the probabilities of the elements being searched for, such a BST will minimize the expected search cost.
Greedy Won’t Work
Cannot apply Huffman algorithm because it assumes that all keys must be at leaves. Alternative greedy algorithm: Always pick the heaviest key as root, then recursively build the tree top-down.
T was built using greedy strategy and has cost
T’hasasmallercost 𝐵 𝑇′ =0.4⋅2+0.3⋅1+0.2⋅2+0.1⋅3=1.8
𝐵 𝑇 =0.4⋅1+0.3⋅2+0.2⋅3+0.1⋅4=2
Dynamic Programming: The Recurrence
Let , be some tree on the subset of nodes
The cost is well defined as
Suppose we knew root of , was
, is a BST, so left and right sub-tree children of
,
are some tree , on and some tree , on
Nodes in , and , are one level deeper in , than in their original trees. So the cost of ,
𝑖 𝑗
, =( ,
, )
, , , ,
Dynamic Programming: The Recurrence
Let , be some tree on the subset of nodes
The cost is well defined as Let Suppose we knew root of , The cost of , is
, = , ,
,
𝑖 𝑗
In particular, suppose , has root and is a minimum cost tree over all trees
with nodes
its left subtree , must be a minimum cost tree with nodes
If it wasn’t, we could replace , by a lesser cost subtree with nodes
By (*), this would reduce , , contradicting that , is a minimum cost tree.
Similarly, the right subtree , must be minimum cost for
Dynamic Programming: The Recurrence
Def: the minimum cost of any BST on
Idea: The root of the BST can be any of . We try each of them.
Recurrence:
Suppose we knew min-cost BST , for [i,j] and that its root was
Its left subtree , must be optimal for [i,k-1]
and its right subtree , must be optimal for [k+1,j]
, ,
𝑖 𝑗
pre-computed in time.
Dynamic Programming: The Recurrence
Def: the minimum cost of any BST on Idea: The root of the BST can be any of
. We try each of them.
Recurrence:
𝑖 𝑗
The Algorithm
Idea: We will do the bottom-up computation by the increasing order of the problem size.
let 𝑒[1..𝑛,1..𝑛],𝑤[1..𝑛,1..𝑛],𝑟𝑜𝑜𝑡[1..𝑛,1..𝑛] be new arrays of all 0
for 𝑖=1 to 𝑛 𝑤𝑖,𝑖 ←𝑓𝑎
for 𝑗=𝑖+1 to 𝑛
𝑤𝑖,𝑗 ←𝑤𝑖,𝑗−1 +𝑓(𝑎)
for 𝑙←1 to 𝑛
for 𝑖←1 to 𝑛−𝑙+1
for 𝑘←𝑖 to 𝑗
𝑡←𝑒 𝑖,𝑘−1 +𝑒[𝑘+1,𝑗]+𝑤[𝑖,𝑗] if 𝑡<𝑒[𝑖,𝑗] then
𝑟𝑜𝑜𝑡𝑖,𝑗 ←𝑘 return Construct-BST(𝑟𝑜𝑜𝑡,1,𝑛)
computation of 𝑤 𝑖,𝑗
length of [i,j] First node Last node
Root k that
𝑒𝑖,𝑘−1 +𝑒[𝑘+1,𝑗]+𝑤[𝑖,𝑗]
Running time: Space:
Construct the Optimal BST
Construct-BST(𝑟𝑜𝑜𝑡, 𝑖, 𝑗): if 𝑖>𝑗 then return 𝑛𝑖𝑙 create a node 𝑧
𝑧.𝑘𝑒𝑦 ← 𝑎[𝑟𝑜𝑜𝑡 𝑖,𝑗 ]
𝑧.𝑙𝑒𝑓𝑡← Construct-BST(𝑟𝑜𝑜𝑡,𝑖,𝑟𝑜𝑜𝑡𝑖,𝑗 −1) 𝑧.𝑟𝑖𝑔h𝑡← Construct-BST(𝑟𝑜𝑜𝑡,𝑟𝑜𝑜𝑡𝑖,𝑗 +1,𝑗) return 𝑧
Running time of this part:
Worked example of the Optimal BST Problem
20 20 B E G 10
Optimal (min-cost) given input
Its cost is
5*4 + 20*3 + 30*2 + 50*1 + 10*3 + 20*2 + 10*3 = 290
Worked example of the Optimal BST Problem
Recurrence: Initial Conditions:
𝑒1,1=𝑓𝑎 =5 𝑒2,2=𝑓𝑎 =20 𝑒3,3=𝑓𝑎 =30 𝑒4,4=𝑓𝑎 =50 𝑒5,5=𝑓𝑎 =10 𝑒6,6=𝑓𝑎 =20 𝑒77=𝑓𝑎 =10
• 𝑟𝑜𝑜𝑡1,1=1 • 𝑟𝑜𝑜𝑡2,2=2 • 𝑟𝑜𝑜𝑡3,3=3 • 𝑟𝑜𝑜𝑡4,4=4 • 𝑟𝑜𝑜𝑡5,5=5 • 𝑟𝑜𝑜𝑡6,6=6 • 𝑟𝑜𝑜𝑡7,7=7
𝑒 1,2 = min 𝑒 1,𝑘−1 +𝑒 𝑘+1,2 +𝑤 1,2 =min 45,30 =30
𝑒 2,3 = min 𝑒 2,𝑘−1 +𝑒 𝑘+1,3 +𝑤 2,3 =min 80,70 =70
𝑒 3,4 = min 𝑒 3,𝑘−1 +𝑒 𝑘+1,4 +𝑤 3,4 =min 130,110 =110
𝑒 4,5 = min 𝑒 4,𝑘−1 +𝑒 𝑘+1,5 +𝑤 4,5 =min 70,110 =70
𝑒 5,6 = min 𝑒 5,𝑘−1 +𝑒 𝑘+1,6 +𝑤 5,6 =min 50,40 =40
𝑒 6,7 = min 𝑒 6,𝑘−1 +𝑒 𝑘+1,7 +𝑤6 ,7 =min 40,50 =40
• 𝑟𝑜𝑜𝑡1,2=2 • 𝑟𝑜𝑜𝑡2,3=3 • 𝑟𝑜𝑜𝑡3,4=4 • 𝑟𝑜𝑜𝑡4,5=4 • 𝑟𝑜𝑜𝑡5,6=6 • 𝑟𝑜𝑜𝑡6,7=6
BCDDFF ABCEEG
𝑒 1,3 = min 𝑒 1,𝑘−1 +𝑒 𝑘+1,3 +𝑤 1,3 =min 125,90,85 =85
𝑒 2,4 = min 210,170,170 = 170
𝑒 3,5 = min 160,130,200 = 130
𝑒 4,6 = min 120,150,150 = 120
𝑒5,7 = min 80,60,80 =60
CCDDF BBDCEFEG
• 𝑟𝑜𝑜𝑡1,3=3
• 𝑟𝑜𝑜𝑡2,4=3
• 𝑟𝑜𝑜𝑡3,5=4
• 𝑟𝑜𝑜𝑡4,6=4
• 𝑟𝑜𝑜𝑡5,7=6
𝑒1,4 = min 𝑒1,𝑘−1 +𝑒𝑘+1,4 +𝑤1,4
= min
= min
30 + 50 + 105,
𝑒 1,0 +𝑒 2,4 +105,
𝑒 1,2 +𝑒 4,4 +105, 0 +170 +105,
𝑒 1,1 +𝑒 3,4 +105, 𝑒 1,3 +𝑒 5,4 +105
5+110+105, 85 + 0 + 105
= min 275, 220,185,190
𝑒 1,4 = min 𝑒 1,𝑘−1 +𝑒 𝑘+1,4 +𝑤 1,4 =min 275,220,185,190 =185
𝑒 2,5 = min 240,200,190,280 = 190 𝑒 3, 6 = min 230,180, 240, 240 = 180
𝑒 4, 7 = min 150,180, 170, 210 = 150
• 𝑟𝑜𝑜𝑡1,4= 3
• 𝑟𝑜𝑜𝑡2,5= 4
• 𝑟𝑜𝑜𝑡3,6= 4
• 𝑟𝑜𝑜𝑡4,7= 4
C DDD BDCECFF ABEEG
𝑒 1,5 = min 𝑒 1,𝑘−1 +𝑒 𝑘+1,5 +𝑤 1,5 =min 305,250,215,210,300 =210
𝑒 2,6 = min 310,270,240,320,320 = 240 𝑒 3,7 = min 270,210,270,260,300 = 210
• 𝑟𝑜𝑜𝑡1,5= 4
• 𝑟𝑜𝑜𝑡2,6= 4
• 𝑟𝑜𝑜𝑡3,7= 4
DDD CE CFCF BBEEG
𝑒 1,6 = min 𝑒 1,𝑘−1 +𝑒 𝑘+1,6 +𝑤 1,6 =min 375,320,285,260,340,345 =260
𝑒 2,7 = min 350,310,270,350,340,380 = 270
• 𝑟𝑜𝑜𝑡1,6= 4
• 𝑟𝑜𝑜𝑡2,7= 4
DD CF CF BE BEG
𝑒 1,7 = min 𝑒 1,𝑘−1 +𝑒 𝑘+1,7 +𝑤 1,7 =min 415,360,325,290,370,365,405 =290
Optimal Tree: Cost = 290
20 20 B E G 10
30 C F 5A 10
• 𝑟𝑜𝑜𝑡1,7= 4
𝑒 1,7 = min 𝑒 1,𝑘−1 +𝑒 𝑘+1,7 +𝑤 1,7 =min 415,360,325,290,370,365,405 =290
Optimal Tree: Cost = 290
20 B E G 10
• 𝑟𝑜𝑜𝑡1,7=4(D)
• 𝑟𝑜𝑜𝑡1,3=3(C)
• 𝑟𝑜𝑜𝑡5,7=6(F)
• 𝑟𝑜𝑜𝑡1,2=2(B)
• 𝑟𝑜𝑜𝑡1,1=1(A)
• 𝑟𝑜𝑜𝑡5,5=5(E)
• 𝑟𝑜𝑜𝑡7,7=7(G)
Interval DP: Matrix-Chain Multiplication
The product of two matrices (with dimensions and Generating requires
) is a matrix .
scalar multiplications.
Given matrices , with entries , ,, the entries in the product matrix
Diagrams on this and the next few pages modified from http://ramos.elo.utfsm.cl/~lsb/elo320/aplicaciones/aplicaciones/CS460AlgorithmsandComplexity/lecture17
Matrix-Chain Multiplication – 3 Matrices
The product of two matrices
(with dimensions and
Calculating any one entry in
so generating × requires
× and ×
) is a matrix × with
× requires scalar multiplications, scalar multiplications (sm).
For three matrices (e.g., ×, × and ×) there are 2 ways to parenthesize:
× ×
General problem: Given a sequence or chain
determine the optimal way to parenthesize
(i.e., the solution with the minimum number of scalar multiplications).
of n matrices,
Matrix-Chain Multiplication – 5 Matrices
5×5 5×4 4×8 8×2 5×2
There are 5 different ways to multiply ABCD together
1. (A(B(CD)))
2. (A((BC)D))
3. ( (AB) (CD) )
4. ((A(BC))D)
5. (((AB)C)D)
5×5 5×4 4×8 8×2
5×4 4×2 5×2
Matrix-Chain Multiplication – 5 Matrices
5×5 5×4 4×8 8×2 5×2
There are 5 different ways to multiply ABCD together
1. (A(B(CD)))
2. (A((BC)D))
3. ( (AB) (CD) )
4. ((A(BC))D)
5. (((AB)C)D)
1. 5(5)2 + 5(4)2 + 4(8)2 = 154 2. 5(5)2 + 5(4)8 + 5(8)2 = 290 3. 5(5)4 + 4(8)2 + 5(4)2 = 204 4. 5(5)8 + 5(4)8 + 5(8)2 = 440 5. 5(5)4 + 5(4)8 + 5(8)2 = 340
Recall: Multiplying
p×q and q×r matrices requires p×q×r multiplications
And yields a p×r matrix
5×5 5×4 4×8 8×2
5×4 4×2 5×2
Problem Definition
• Input: Values
• These represent sizes of n matrices
Matrix has dimensions
• ⋯ : matrix that is the product of
By construction ⋯ has dimensions
• Goal: To find a minimum cost way of multiplying
to get the final result ⋯.
cost = # of total scalar multiplications performed
This is known as an optimal parenthesization of
because the parentheses denote how to perform the multiplications e.g., ( ( ) ( ) ) means first calculate , then calculate and finally calculate .
⋯ : denotes matrix that results from the product
Optimal Solution Structure
Given: Values s.t. Matrix has size
An (optimal) parenthesization of between and for some integer
splits the product where .
⋯= ⋯ ⋯
In the optimal parenthesization,
1st : compute matrices ⋯ and ⋯ ;
2nd : multiply ⋯ and ⋯ together to get final matrix ⋯
Observation: If parenthesization of is optimal => parenthesizations of subchains and
must also be optimal (why?)
=> The optimal solution to the problem contains within it the optimal solution to subproblems
Recurrence
=minimum number of scalar multiplications necessary to compute
Suppose the optimal parenthesization of ⋯ splits product between and , for some integer k,
⋯= ⋯⋯
min cost of computing ⋯ = min cost of computing ⋯ + min cost
of computing ⋯ + cost of multiplying ⋯ and ⋯
Cost of multiplying ⋯ and ⋯ is
But… optimal parenthesization occurs at some value of k. Check all possible values of k and select the best one.
DP Algorithm
Input: Array p[0…n] containing matrix dimensions and n Result: Minimum-cost table m and split table s
(s records values of k at which minima occurred)
MATRIX-CHAIN-ORDER(p[ ], n) for i = 1 to n
Initial Conditions
Recurrence Relation
Location of Minimum
Timeis𝑂 𝑛 ,spaceis𝑂 𝑛
Matrix Multiplication Worked Example
These represent sizes of n matrices Matrix has dimensions
⋯ : matrix product of ⋯ has dimensions
= minimum number of scalar multiplications required to compute
Recurrence
= records values of k at which minimum occurs
𝑚𝑖,𝑗 = min 𝑖,𝑘 +𝑚𝑘+1,𝑗 + 𝑝𝑝𝑝
𝑚𝑖,𝑗 = min 𝑖,𝑘 +𝑚𝑘+1,𝑗 + 𝑝𝑝𝑝
𝑚𝑖,𝑗 = min 𝑖,𝑘 +𝑚𝑘+1,𝑗 + 𝑝𝑝𝑝
𝑚1,1 =0 𝑚2,2 =0 𝑚3,3 =0 𝑚4,4 =0 𝑚5,5 =0
𝑚𝑖,𝑗 = min 𝑖,𝑘 +𝑚𝑘+1,𝑗 + 𝑝𝑝𝑝
𝑨𝟏 𝑨𝟐 • 𝑚2,3 =𝑚2,2 +𝑚3,3 +4∗6∗2=48 𝑨𝟐𝑨𝟑
• 𝑚3,4 =𝑚3,3 +𝑚4,4 +6∗2∗7=84 𝑨𝟑𝑨𝟒
• 𝑚4,5 =𝑚4,4 +𝑚5,5 +2∗7∗4= 𝑨𝟒𝑨𝟓 56
𝑚1,2 =𝑚1,1 +𝑚2,2 +5∗4∗6=120
𝑚𝑖,𝑗 = min 𝑖,𝑘 +𝑚𝑘+1,𝑗 + 𝑝𝑝𝑝
𝑚1,3 =min 𝑚1,1 +𝑚2,3 +5∗4∗2, =88 𝑚 1,2 +𝑚 3,3 +5∗6∗2
𝑚2,4 =min 𝑚2,2 +𝑚3,4 +4∗6∗7, =104 𝑚 2,3 +𝑚 4,4 +4∗2∗7
𝑚3,5 =min 𝑚3,3 +𝑚4,5 +6∗2∗4, =104 𝑚 3,4 +𝑚 5,5 +6∗7∗4
𝑨𝟏𝑨𝟐..𝟑 𝑨𝟐..𝟑𝑨𝟒
𝑚𝑖,𝑗 = min 𝑖,𝑘 +𝑚𝑘+1,𝑗 + 𝑝𝑝𝑝
𝑚 1,4 =min
𝑚 1,1 +𝑚 2,4 +5∗4∗7
𝑚 1,2 +𝑚 3,4 +5∗6∗7 =158
𝒎 𝟏,𝟑 +𝒎 𝟒,𝟒 +𝟓∗𝟐∗𝟕
𝑚 2,2 +𝑚 3,5 +4∗6∗4
𝑚2,5 =min 𝒎𝟐,𝟑 +𝒎𝟒,𝟓 +𝟒∗𝟐∗𝟒 =136
𝑚 2,4 +𝑚 5,5 +4∗7∗4
𝑨𝟐..𝟑𝑨𝟒..𝟓
𝑚𝑖,𝑗 = min 𝑖,𝑘 +𝑚𝑘+1,𝑗 + 𝑝𝑝𝑝
𝑚 1,4 +𝑚 5,5 +5∗7∗4,
𝑚1,5 =max 𝒎𝟏,𝟑 +𝒎𝟒,𝟓 +𝟓∗𝟐∗𝟒, =184
𝑚 1,2 +𝑚 3,5 +5∗6∗4, 𝑚 1,1 +𝑚 2,5 +5∗4∗4
𝑚𝑖,𝑗 = min 𝑖,𝑘 +𝑚𝑘+1,𝑗 + 𝑝𝑝𝑝
Optimal solution is
(𝑨𝟏..𝒔[𝟏,𝟓]𝑨𝒔 𝟏,𝟓 𝟏..𝟓) = (𝑨𝟏..𝟑𝑨𝟒..𝟓)
= (𝑨𝟏..𝒔[𝟏,𝟑]𝑨𝒔 𝟏,𝟑 𝟏..𝟓)𝑨𝟒..𝟓 = ( 𝑨𝟏..𝟏𝑨𝟐..𝟑 𝑨𝟒..𝟓)
= ((𝑨𝟏(𝑨𝟐..𝒔 𝟐,𝟑 𝑨𝒔 𝟐,𝟑 𝟏..𝟑))𝑨𝟒..𝟓) = ((𝑨𝟏(𝑨𝟐..𝟐𝑨𝟑..𝟑))𝑨𝟒..𝟓)
= ((𝑨𝟏(𝑨𝟐𝑨𝟑))𝑨𝟒..𝟓)
= ((𝑨𝟏(𝑨𝟐𝑨𝟑))(𝑨𝟒..𝒔 𝟒,𝟓 𝑨𝒔 𝟒,𝟓 𝟏,𝟓))
= ((𝑨𝟏(𝑨𝟐𝑨𝟑))(𝑨𝟒𝑨𝟓))
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com