演算法›Ch3 動態規劃第 30 題/共 40 題
30. Matrix Chain Multiplication、Dynamic Programming、Pseudocode 填空
#AL-03-030易Matrix Chain MultiplicationDynamic ProgrammingPseudocode 填空
(10%) The following procedure is a bottom-up method for matrix chain order. This procedure assumes that matrix has dimensions for . Its input is a sequence , where . Let be the minimum number of scalar multiplications needed to compute the matrix . The procedure uses an auxiliary table for storing the costs and another auxiliary table that records which index of achieved the optimal cost in computing . Please fill in the empty statements.
n = p.length - 1
let m[1..n,1..n] and s[1..n-1,2..n] be new tables
for i = 1 to n
m[i,i] = 0
for l = 2 to n // l is the chain length
for i = 1 to n-l+1
j = ____(a) (3%)____
m[i,j] = infinity
for k = i to j-1
q = ____(b) (4%)____
if q < m[i,j]
m[i,j] = q
s[i,j] = ____(c) (3%)____
📄 成大112
▤完整推導請見《WH 資工筆記 · 演算法》Ch3 動態規劃