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;
}

Matrix Multiplication Memoized

This is a memoized version of naive recursion.
#include
#include
using namespace std;
#define MAX 1000
int dp[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;
        return 0;
    }
    int i=A[start];
    int j= A[end+1];
    if(end-start==1)
        return i*j*A[end];
    int mini=12345678;
    for(int k=start;k    {
        mini=min(mini,min_cost(A,n,start,k)+min_cost(A,n,k+1,end)+i*A[k+1]*j);
    }
    dp[start][end]=mini;
    return mini;
}
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\n",min_cost(A,n,0,n-2));

return 0;
}

CLRS Dynamic Programming Practice

Its been long since I posted on this blog. I can't believe I made this blog almost 6 years ago. Time flies fast. Memories remain.
So lets get to it. I'm using this blog again as my coding journal. I'll blog whatever my thoughts are and the code I practice :)
 Matrix Chain Multiplication
Given: An array A containing number of rows in each matrix numbered 0 to n-1. n is the number of matrices to be multiplied in a chain. The nth index contains the number of columns in the nth matrix
To calculate: 1.Minimum number of multiplications required to multiply these matrices
2. Where should we insert the parentheses int the given chain to get the optimal ans obtained in 1.

Naive recursive solution:
#include
#include
using namespace std;
int min_cost(int A[],int n,int start,int end)
{
    if(start>=end)
        return 0;
    int i=A[start];
    int j= A[end+1];
    if(end-start==1)
        return i*j*A[end];
    int mini=12345678;
    for(int k=start;k    {
        mini=min(mini,min_cost(A,n,start,k)+min_cost(A,n,k+1,end)+i*A[k+1]*j);
    }
    return mini;
}
int main()
{
int A[]={30,35,15,5,5,10,20,25};
int n= sizeof(A)/sizeof(A[0]);
printf("Minimum number of multiplications required are:%d\n",min_cost(A,n,0,n-2));
return 0;
}

Hi

Hi! Everybody