Optimum order for matrix chain multiplications
Given an array of matrices such that matrix at any index can be multiplied
by the matrix at the next contiguous index, find the best order to
multiply them such that number of computations is minimum.
To multiply 2 contiguous matrices of size PxQ and QxM, computations
required are PxQxM
Example of correct order:
Consider the multiplication of matrices with following dimensions: 4x3 3x2 2x5
They can be multiplied in two ways:
= ((4x3 3x2) 2x5)
= (4x2 2x5), multiplications = 4x3x2 = 24
= 4x5, multiplications = 24 + 4x2x5 = 64
= (4x3 (3x2 2x5))
= (4x3 3x5), multiplications = 3x2x5 = 30
= 4x5, multiplications = 30 + 4x3x5 = 90
Solution: Let each matrix be represented by a letter and let the matrix array be ABCD.
Let result of multiplying matrices P and Q be shown as (PQ)
Then we can choose to multiply matrices in many ways, some of which are as follows:
Whatever be the order of multiplication, the last two matrices to multiply will be contiguous.
And the solution to the problem lies in finding that pair which will be multiplied last.
the idea is that any two contiguous matrices can be multiplied.
consider all the possible cases, we need to do the following:
Multiply 2 matrices at indices k and k+1
Multiply matrices from 0 to k-1 in best possible manner
Multiply matrices from k+1 to N in best possible manner
Multiply all 3 matrices obtained in 3 steps above.
Store the number of computations.
Vary k from 0 to N-1 and choose the combination which yields minimum
us specify an array mtrxSizes whose every 2 contiguous indices will
be used to specify a matrix of size matrxSizes[k] x mtrxSizes[k+1]
to specify N matrices, mtrxSizes has to be of size N+1
above is a recursive solution and since it does not use any DP, many
subproblems are calculated repeatedly.
Dynamic Programming Solution
int minCalcsForMatrices(int p, int n)
// 0th row and 0th column of lookup are not used.
// No cost if there is only one matrix
for (int i = 1; i < n; i++)
lookup[i][i] = 0;
// find solution for increasing group-size of matrices
for (int chainLen=2; chainLen<n; chainLen++)
for (int i=1; i<=n-chainLen+1; i++) // set i as starting of group
int j = i+chainLen-1; // set j as ending of group
lookup[i][j] = Integer.MAX_VALUE;
for (int k=i; k<=j-1; k++) // vary k from i to j
int cost = lookup[i][k] + lookup[k+1][j] + p[i-1]*p[k]*p[j];
if (int cost < lookup[i][j])
lookup[i][j] = int cost;
In terms of loops, note how similar this problem is to:
All of these problems have an outer loop which starts with 1 or 2 elements and then gradually
widens the scope of the problem being solved.
- Max ways for boolean expression to be true
- Longest palindrome creation