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.
Note:
To multiply 2 contiguous matrices of size PxQ and QxM, computations
required are PxQxM
Example:
3x2
A B
D E
G H

2x1
P
Q

3x1
AP+BQ
DP+EQ
GP+HQ

3x2
A B
D E
G H

2x2
P R
Q S

3x2
AP+BQ AR+BS
DP+EQ DR+ES
GP+HQ GR+HS

Example of correct order:
Consider the multiplication of matrices with following dimensions: 4x3 3x2 2x5
They can be multiplied in two ways:
(AB)C

A(BC)

= ((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:
 (((AB)C)D)
 (A((BC)D))
 ((AB)(CD))
 ...
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.
Basically,
the idea is that any two contiguous matrices can be multiplied.
To
consider all the possible cases, we need to do the following:
1)
Multiply 2 matrices at indices k and k+1
2)
Multiply matrices from 0 to k1 in best possible manner
3)
Multiply matrices from k+1 to N in best possible manner
4)
Multiply all 3 matrices obtained in 3 steps above.
5)
Store the number of computations.
6)
Vary k from 0 to N1 and choose the combination which yields minimum
computations.
Let
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]
Thus
to specify N matrices, mtrxSizes has to be of size N+1
The
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.
int lookup[n][n];
// No cost if there is only one matrix
for (int i = 1; i < n; i++)
lookup[i][i] = 0;
// find solution for increasing groupsize of matrices
for (int chainLen=2; chainLen<n; chainLen++)
{
for (int i=1; i<=nchainLen+1; i++) // set i as starting of group
{
int j = i+chainLen1; // set j as ending of group
lookup[i][j] = Integer.MAX_VALUE;
for (int k=i; k<=j1; k++) // vary k from i to j
{
int cost = lookup[i][k] + lookup[k+1][j] + p[i1]*p[k]*p[j];
if (int cost < lookup[i][j])
lookup[i][j] = int cost;
}
}
}
return lookup[1][n1];
}
In terms of loops, note how similar this problem is to:
 Max ways for boolean expression to be true
 Longest palindrome creation
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.
