Matrix Chain Multiplication with Optimal Parenthization

#include
#include
using namespace std;
#define MAX 1000
int dp[MAX][MAX];
int dp2[MAX][MAX];
int min_cost(int A[],int n,int start,int end)
{
    if(dp[start][end]!=-1)
        return dp[start][end];
    if(start==end)
    {   dp[start][end]=0;
    dp2[start][end]=end;
        return 0;
    }
    int i=A[start];
    int j= A[end+1];
    if(end-start==1)
        {
            dp[start][end]=i*j*A[end];
            dp2[start][end]=end;
            return i*j*A[end];
        }
    int mini=12345678;
    int mini_index;
    for(int k=start;k    {
        if(min_cost(A,n,start,k)+min_cost(A,n,k+1,end)+i*A[k+1]*j        {
            mini=min_cost(A,n,start,k)+min_cost(A,n,k+1,end)+i*A[k+1]*j;
            mini_index=k;
        }
    }
    dp[start][end]=mini;
    dp2[start][end]=mini_index;
    return mini;
}
void print(int s,int e)
{
    if(s==e)
        {printf("A%d",s+1);
        return;
        }
    if(e-s==1)
        {printf("(A%d A%d)",s+1,e+1);
        return;
        }
    printf("(");
    print(s,dp2[s][e]);print(dp2[s][e]+1,e);
    printf(")");
}
int main()
{
    for(int i=0;i        for(int j=0;j        dp[i][j]=-1;
int A[]={30,35,15,5,10,20,25};
int n= sizeof(A)/sizeof(A[0]);
printf("Minimum number of multiplications required are:%d\nThe optimal parenthization is: ",min_cost(A,n,0,n-2));
print(0,n-2);

return 0;
}