DP #04. Matrix Chain Multiplication. - mbhushan/dynpro GitHub Wiki
(4). Matrix Chain Multiplication.
Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.
We have many options to multiply a chain of matrices because matrix
multiplication is associative. In other words, no matter how we
parenthesize the product, the result will be the same.
For example, if we had four matrices A, B, C, and D, we would have:
(ABC)D = (AB)(CD) = A(BCD) = ....
However, the order in which we parenthesize the product affects
the number of simple arithmetic operations needed to compute the product,
or the efficiency. For example, suppose A is a 10 × 30 matrix,
B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,
(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.
Clearly the first parenthesization requires less number of operations.
Input:
int [] M = {2, 3, 6, 4, 5};
There are 4 matrices of dimensions (2, 3) (3, 6) (6, 4) and (4, 5)
Formula is:
T[i][j] = Min (
T[i][k] + T[k][j] + (M[i] * M[k] * M[j]); //for i+1 <= k < j
);
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 36 | 84 | 124 |
| 1 | 0 | 72 | 132 | |
| 2 | 0 | 120 | ||
| 3 | 0 |
public int matrixMulChainCost(int [] M) {
int len = M.length;
/* m[i,j] = Minimum number of scalar multiplications needed
to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where
dimension of A[i] is p[i-1] x p[i] */
int [][] T = new int[len][len];
int value = 0;
for (int n=2; n<len; n++) {
for (int i=0; i<len-n; i++) {
int j = i + n;
T[i][j] = Integer.MAX_VALUE;
for (int k=i+1; k<j; k++) {
value = T[i][k] + T[k][j] + (M[i] * M[k] * M[j]);
if (value < T[i][j]) {
T[i][j] = value;
}
}
}
}
return T[0][len-1];
}
- Time Complexity: O(n^3)
- Space Complexity: O(n^2)