设计递归算法MATRIX-CHAIN-MULTIPLY(A,s,i,j),实现矩阵链最优化代价乘法计算的真正计算过程,其输入参数为矩阵序列<A1,A2,...,An>,MATRIX-CHAIN-ORDER得到的表s,以及下标i和j。(初始调用应为MATRIX-CHAIN-MULTIPLY(A,s,1,n)。)
MATRIX-CHAIN-ORDER(p) n = p.length - 1 let m[1..n,1..n] and s[1..n-1,2..n] be a new array 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 = i + l -1 m[i,j] = \inf for k = i to j-1 q = m[i,k] + m[k+1,j] + p[i-1]p[k]p[j] if q < m[i,j] m[i,j] = q s[i,j] = k return m,s