Предполагается

матрица A_i имеет размер p_i-1 × p_i при i = 1,2,2,…,n

на входе последовательность

 

length[p] = n+1

Используются вспомогательные таблицы

m[1..n,1..n]

s[1..n,1..n]

 

Matrix-Chain-Order (p)

1 n ¬ length[p] - 1

2 for i ¬ 1 to n

3 do m[i,i] ¬ 0

4 for l ¬ 2 to n

5 do for i ¬ 1 to n – l +1

6 doj ¬ i + l - 1

7 m[i, j] ¬ ∞

8 for k ¬ i toj –1

9 do q ¬ m[i,k]+m[k + 1,j] + p_i-1 p_k p_j

10 if q < m[i,j]

11 thenm[i,j] ¬ q

12s[i,j] ¬ k

13 returnm, s

 

Шаг 4: построение оптимального решения

Matrix-Chain-Multiply (A,s,i,j)

1 if j > i

2 thenX ¬ Matrix-Chain-Multiply (A,s,i, s[i,j])

3 Y ¬ Matrix-Chain-Multiply (A,s, s[i,j]+1 ,j)

4 returnMatrix-Multiply (X, Y)

5 else returnA