mcm

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
void input();
int Matrix_Chain_Order(int [],int);
void Print_Optimal_Parents(int [100][100], int, int);

int i,j,k,l,n,q,val,length,numofmatrix,firstValue,count=1;
int mat[100], m[100][100],s[100][100],p[100];
void input()
{
    printf("Number of matrix:");
    scanf("%d", &numofmatrix);
    int index = 0;
    for(i=1; i<=(numofmatrix*2); i=i+2)
    {

        printf("MATRIX A%d\n", count++);
        printf("number of row:");
        scanf("%d",&mat[i]);
        printf("number of column:");
        scanf("%d", &mat[i+1]);

    }

    firstValue = mat[1];

    for(i=2; i<=(numofmatrix*2); i=i+2)
    {
        index = index+1;
        p[index] = mat[i];
    }

    p[0] = firstValue;

    length = index;
    printf("\nElements in P array: ");
    for(i=0; i<=length; i++)
    {
        printf("%d ", p[i]);
    }
}
int Matrix_Chain_Order(int p[], int length)
{
    n = length;
    for (i=1; i<=n; i++)
    {
        m[i][i] = 0;
    }


    for (l=2; l<=n+1; l++)
    {
        for (i=1; i<=n-l+1; i++)
        {
            j = i+l-1;
            m[i][j] = 1000000;
            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;
                }

            }
        }
    }

    return m[i][j];
}

void Print_Optimal_Parents(int s[100][100],int i, int j)
{
    if(i==j)
    {
        printf(" A%d",i);

    }
    else
    {
        printf("( ");
        Print_Optimal_Parents(s,i,s[i][j]);
        Print_Optimal_Parents(s,s[i][j]+1,j);
        printf(" )");
    }
}

int main()
{
    input();
    val = Matrix_Chain_Order(p,length);
    printf("\n\nCost: %d", val);
    printf("\n\nOptimal Path:\n ");
    Print_Optimal_Parents(s,1,length);
    printf("\n");
    return 0;
}