Matrix chain multiplication

where

A_i

has dimensions

p_{i-1} \times p_i

for multiplication

Parenthesize if important

Suppose that an optimal parenthesiation of

A_{i\dots j}

splits the product beween

A_k

and

A_{k+1}

A_{i\dots j} = A_i\cdots A_j, i\le j

Let

m[i, j]

is the minimum number of multiplications needed to compute

A_{i\cdots j}

m[i,j] = m[i,k] + m[k+1, j] + p_{i-1}p_{k}p_{j}

fill out direction

for calculate minimum, we need for loop so

O(n^3)

So we don’t use DP solution

In reality we use

Heuristic and approximate algorithm