留学生考试辅导 CS460AlgorithmsandComplexity/lecture17

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