/* I HAVE ALLOCATED MEMORY STATICALLY FOR TESTING PURPOSES.

P[ ]={5,4,6,2,7}

means:

matrices of order 5 X 4 , 4 X 6 , 6 X 2 , 2 X 7

check http://w...content-available-to-author-only...t.hk/~dekai/271/notes/L12/L12.pdf

for the dry run and the detailed algorithm.


*/


#include<stdio.h>

int main()
{
        int p[]={5,4,6,2,7};
        int a[5][5];

        

        int i,j,k,gap=1;


        for(i=0;i<5;i++)
                for(j=0;j<5;j++)
                        a[i][j]=30000;

    for(gap=0;gap<5;gap++)
    {   
         for(i=1,j=i+gap ; i<5 && j<5 ; i++,j++)
         {
                if(i==j) a[i][i]=0;
                else
                {

                        for(k=i;k<j;k++)
                        {
                               int val=a[i][k]+a[k+1][j] + p[i-1]*p[k]*p[j];
                               if(val<a[i][j])
                               {
                                a[i][j]=val;

                               }
                        }
                         
               }

          }
       
     }

     for(i=1;i<5;i++)
     {   for(j=1;j<5;j++)
         {         
                    if(a[i][j]==30000) printf("\tX");
                    else printf("\t %d",a[i][j]);

          }
        printf("\n") ;
     }return 0;
}