matrix chain multiplication implementation with c

matrix chain multiplication is a great and easy algorithm.it consists of two parts matrix chain order and print optimal output.

if you love to see this share about us and also request for codes in comments section.

thankyou

#include<stdio.h>

#include<stdlib.h>

void input(int *p,int n)


int i;

printf(“\nEnter the order of the matrices:”);

for(i=0;i<=n;i++)

scanf(“%d”,(p+i));

printf(“\nThe p array is:”);

for(i=0;i<=n;i++)

printf(“%d\t”,*(p+i));

void matrix_chain_order(int *p,int n,int **m,int **s)


int i,l,j,k,q;

for(i=1;i<=n;i++)

m[i][i]=0;

for(l=2;l<=n;l++)


for(i=1;i<=n-l+1;i++)


j=i+l-1;

m[i][j]=99999;

for(k=i;k<=j-1;k++)


q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

if(q<m[i][j])


m[i][j]=q;

s[i][j]=k;

void print_optimal_parens(int **s,int i,int j)


if(i==j)

printf(“A[%d]”,i);

else


printf(“(“);

print_optimal_parens(s,i,s[i][j]);

print_optimal_parens(s,s[i][j]+1,j);

printf(“)”);

void output(int **m,int **s,int n)


int i,j;

printf(“\nThe m table is:\n”);

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

printf(“%d\t”,m[j][i]);

printf(“\n”);

printf(“\nThe s table is:\n”);

for(i=2;i<=n;i++)

for(j=1;j<i;j++)

printf(“%d\t”,s[j][i]);

printf(“\n”);



int main()


int *p,n,i;

int **m,**s;

printf(“How many matrices you want to multiply:”);

scanf(“%d”,&n);

p=(int *) malloc (sizeof(int) * (n+1));

input(p,n);

m=(int **) malloc (sizeof(int *)*(n+1));

for(i=0;i<=n;i++)

*(m+i)=(int *) malloc (sizeof(int) *(n+1));

s=(int **) malloc (sizeof(int *)*(n-1));

for(i=0;i<=n;i++)

*(s+i)=(int *) malloc (sizeof(int) *(n+1));

matrix_chain_order(p,n,m,s);

print_optimal_parens(s,1,n);

output(m,s,n);

return 0;

matrix chain multiplication implementation with c