#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int Optimal(int **A, int *B, int n);
int main()
{
     int n, **A,*B,i,m,j,k;
     printf("n Enter the number of natrices to be multiplied :");
     scanf("%d",&n);

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

     {
          for(i=0; i<=n; i++)
          {        A[i] = (int *)malloc(n*sizeof(int));
                   for( j=0; j<=n; j++)
                   {
                            A[i][j]=0;
                   }
          }

     }
    printf("n Array entered :n");
     for(i=1;i<=n;i++)
     {
          for(j=1; j<=n; j++)
          {
               printf("%d ", A[i][j]);

          }
          printf("n");
     }

 B =(int *)malloc((n+1)*sizeof(int));
for(i=0;i<=n;i++)
{   printf("Input the Columns of Matrix %d and Rows of %d",i,i+1);
    scanf("%d",&m);
    B[i]=m;
}

Optimal(A,B,n);
printf("The Minimum Number of Calculations required is %d ",A[1][n]);


return 0;
}

int Optimal(int **A, int *B, int n)
{
     int m=50000,j,i,k;
  for(i=1;i<=n;i++)
         {
             A[i+1][i]=B[i+1]*B[i]*B[i-1];
         }
  for(k=2;k<n;k++)
    {

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

              for(j=1;j<k;j++)
              if(m<A[i+k][i+k-j]*A[i+k-j-1][i]+B[i+k]*B[i+k-j-1]*B[i])
              {
                   m=A[i+k][i+k-j]*A[i+k-j-1][i]+B[i+k]*B[i+k-j-1]*B[i];
              }
              A[i+k][i]=m;
         }
    }

return 0;
}