-
Notifications
You must be signed in to change notification settings - Fork 0
/
MCM_dp.java
69 lines (53 loc) · 2.06 KB
/
MCM_dp.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
Code : MCM
Send Feedback
Given a chain of matrices A1, A2, A3,.....An, you have to figure out the most efficient way to multiply these matrices i.e. determine where to place parentheses to minimise the number of multiplications.
You will be given an array p[] of size n + 1. Dimension of matrix Ai is p[i - 1]*p[i]. You need to find minimum number of multiplications needed to multiply the chain.
Input Format :
Line 1 : Integer n i.e. number of matrices
Line 2 : n + 1 integers i.e. elements of array p[]
Output Format :
Line 1 : Minimum number of multiplication needed
Constraints :
1 <= n <= 100
Sample Input 1 :
3
10 15 20 25
Sample Output :
8000
Sample Output Explanation :
There are two ways to multiply the chain - A1*(A2*A3) or (A1*A2)*A3.
If multiply in order A1*(A2*A3) then number of multiplications required are 15000.
If multiply in order (A1*A2)*A3 then number of multiplications required are 8000.
Thus minimum number of multiplications required are 8000
public class Solution {
public static int mcm(int[] p){
return MatrixChainOrder(p, p.length);
}
static int MatrixChainOrder(int p[], int n)
{
int m[][] = new int[n][n];
int i, j, k, L, q;
/* 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] */
// cost is zero when multiplying one matrix.
for (i = 1; i < n; i++)
m[i][i] = 0;
// L is chain length.
for (L = 2; L < n; L++) {
for (i = 1; i < n - L + 1; i++) {
j = i + L - 1;
if (j == n)
continue;
m[i][j] = Integer.MAX_VALUE;
for (k = i; k <= j - 1; k++) {
// q = cost/scalar multiplications
q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n - 1];
}
}