Matrix chain multiplication using dynamic programming C code

 

Matrix  chain multiplication using dynamic programming C code

Consider three matrices of 

matrix        Order

A                 5*4

B                 4*3

C                 3*5

Possible multiplication

((AB)C)=(5*4*3)+(5*3*5)=135

(A(BC))=(5*4*5)+(4*3*5)=160

optimal multiplication=((AB)C)

#include<stdio.h>

int m[10][10];

int i,j,n,d,k,r,l,z;

int mcm(int p[],int n);

int main()

{

  int  p[]={5,4,3,5};

    n=sizeof(p)/sizeof(p[0]);

    printf("Minimum number of multiplication required %d",mcm(p,n));

    getchar();

    return 0;

    }

int mcm(int p[],int n)

{

  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]=9999999;

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

        {

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

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

                m[i][j]=r; 

        }

    } 

  }

  return m[1][n-1];

}

Output

Minimum number of multiplication required 135