演算法›Ch3 動態規劃
第 30 題/共 40 題
◀ AL 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 AiA_i has dimensions pi−1×pip_{i-1} \times p_i for i=1,2,...,ni = 1, 2, ..., n. Its input is a sequence p=⟨p0,p1,...,pn⟩p = \langle p_0, p_1, ..., p_n \rangle, where p.length=n+1p.length = n+1. Let m[i,j]m[i,j] be the minimum number of scalar multiplications needed to compute the matrix AiAi+1⋯AjA_i A_{i+1} \cdots A_j. The procedure uses an auxiliary table m[1..n,1..n]m[1..n, 1..n] for storing the m[i,j]m[i,j] costs and another auxiliary table s[1..n−1,2..n]s[1..n-1, 2..n] that records which index of kk achieved the optimal cost in computing m[i,j]m[i,j]. 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 動態規劃
本章題號 · 21–40 / 40