问题描述

给定n个矩阵的链<A1，A2，...，An>，矩阵Ai的规模为pi-1xpi（1 <= i <= n），求完全括号化方案，是的计算成绩A1A2...An所需标量乘法次数最少。

计算最优代价——时间：（Ω(n³)），空间：（Θ(n²)）

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 ")"
}