**DP - Matrix chain multiplication (MCM)**

Last Update: 6 March, 2009

**Problem:**
Matrix chain multiplication is an optimization problem that can
be solved using dynamic programming. Given a sequence of
matrices, we want to 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 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) = A(BC)D = ....

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 x 30
matrix, B is a 30 x 5 matrix, and C is a 5 x 60 matrix. Then,

(AB)C = (10x30x5) + (10x5x60) = 1500 + 3000 = 4500 operations

A(BC) = (30x5x60) + (10x30x60) = 9000 + 18000 = 27000
operations.

Clearly the first method is the more efficient. Now that we have
identified the problem, how do we determine the optimal
parenthesization of a product of n matrices? We could go through
each possible parenthesization (brute force), but this would
require time O(2n), which is very slow and impractical for large
n. The solution, as we will see, is to break up the problem into
a set of related subproblems. By solving subproblems one time
and reusing these solutions many times, we can drastically
reduce the time required. This is known as dynamic programming.

```
//C++ Code for Matrix Chain Multiplicatio
//ACM 34
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cctype>
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
#define INF 1047483647
#define EPS 0.000000001
#define MAX(a,b) ((a>b)?a:b)
#define MIN(a,b) ((a<b)?a:b)
#define CLEAR(A,N) (memset(A,0,(N)*sizeof(A[0])))
#define VI vector<int>
int mcm[20][20],path[20][20];
int findMCM(int i, int j, int P[]) {
int k,q;
if(mcm[i][j]<INF)
return mcm[i][j];
if(i==j)
mcm[i][j]=0;
else{
for(k=i;k<j;k++){
q = findMCM(i,k,P) + findMCM(k+1,j,P) + P[i-1]*P[k]*P[j];
if(q<mcm[i][j]){
mcm[i][j]=q;
path[i][j]=k;
}
}
}
return mcm[i][j];
}
void pathOfMCM(int i, int j) {
if(i==j){
printf("A%d",i);
return;
}
printf("(");
pathOfMCM(i,path[i][j]);
printf(" x ");
pathOfMCM(path[i][j]+1,j);
printf(")");
}
void initMatrix(int N){
int i,j;
for(i=0;i<=N;i++){
for(j=0;j<=N;j++){
mcm[i][j]=INF;
path[i][j]=0;
}
}
}
int main()
{
//freopen("in.txt","rt",stdin)
//freopen("out.txt","wt",stdout)
int P[20],a,b,i,j,N,t=0;
while(scanf("%d",&N)==1 && N!=0) {
j=0;
for(i=0;i<N;i++){
scanf("%d %d",&a,&b);
P[j++]=a;
}
P[j]=b;
initMatrix(N);
a=findMCM(1,N,P);
//cout<
printf("Case %d: ",++t);
pathOfMCM(1,N);
printf("\n");
}
// End of main function.......
return 0;
}
/*** Programmed by:
###########################
## ~ ORONNO ~ ##
## Team-: "Gladiator" ##
## CSEDU 12th Batch. ##
###########################
Note: This program is not totally
useless. Because, at least, this
might be used as a bad example!!!!
**********************************/
```