CODEWITHSUNDEEP
algorithmmatrixdynamic-programming
user2895506
user2895506

Reputation: 11

Matrix multiplicatiion

I was reading Introduction to Algorithms by Cormen on dynamic programming.

The ordering of matrices is important to perform a matrix multiplication. If I multiplied a number of matrices and come up with the best result, how to keep that result optimal by adding a matrix to the series ?

Upvotes: 1

Views: 85

Answers (1)

IVlad
IVlad

Reputation: 43477

If you have:

DP[i, j] = minimum cost of multiplying matrices i to through j

then DP[1, n] will be your answer.

To find DP[1, n + 1], just apply the same recurrence you used to build the table:

DP[1, n + 1] = min   {DP[1, k] + DP[k + 1, n + 1] + multiplication cost}
            1<=k<n+1

This will be O(n).

Upvotes: 1

Related Questions