Matrix chain multiplication using dynamic programming(Top Down Approach)
1 min readAug 13, 2019
#include<iostream>
#include<limits.h>
using namespace std;
int P[]={1,2,1,4,1,3,1};
int M[10][10];
void Min_Matrix_Mul(int a,int b){
if(a==b){
M[a][b]=0;
}
else{
int p[b-a];
for(int i=a;i<b;i++){
int x,y,z;
if(M[a][i]!=INT_MAX){
x=M[a][i];
}
else{
Min_Matrix_Mul(a,i);
x=M[a][i];
}
if(M[i+1][b]!=INT_MAX){
y=M[i+1][b];
}
else{
Min_Matrix_Mul(i+1,b);
y=M[i+1][b];
}
z=P[a-1]*P[i]*P[b];
if(M[a][b]>x+y+z){
M[a][b]=x+y+z;
}
}
}
}
int main()
{
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
M[i][j]=INT_MAX;
int Number=sizeof(P)/sizeof(int)-1;
int a=1;
Min_Matrix_Mul(a,Number);
for(int i=1;i<Number+1;i++){
for(int j=1;j<Number+1;j++){
if(i>j){
cout<<” \t”;
}
else if(M[i][j]==INT_MAX){
cout<<”0\t”;
}
else
{
cout<<M[i][j]<<”\t”;
}
} cout<<”\n”;
}
}
