问题描述
给定n个矩阵的链<A1，A2，...，An>，矩阵Ai的规模为pi-1xpi（1 <= i <= n），求完全括号化方案，是的计算成绩A1A2...An所需标量乘法次数最少。
计算最优代价——时间：（Ω(n3)），空间：（Θ(n2)）
MATRIX-CHAIN-PRDER (p){
n = p.length - 1
let m[1...n, 1...n] and s[1...n, 1...n] be new tables
for i = 1 to n
m[i, i] = 0
for i= 2 to n
for i = 1 to n-l+1
j = i+l-1
m[i, j] = ∞
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 and s
}
构造最优解
PRINT-OPTIMAL-PARENS(s, i, j){
if i == j
print "A"_i
else print "("
PRINT-OPTIMAL-PARENS(s, i, s[i, j])
PRINT-OPTIMAL-PARENS(s, s[i, j]+1, j)
print ")"
}
