Matrix Chain Multiplication (Dynamic Programming)

Matrix Chain Multiplication (Dynamic Programming)

Problem statement: Given a chain of n matrices (A1 A2 A3 ..... An), matrix Ai has dimension ( pi-1 x pi ) fully parenthesize the product A1A2A3......An in a way that minimizes the number of scalar multiplication.

The program below is one of the best ways to do so.

#define INF 2143483647
#define MAX 20
int m[MAX][MAX],s[MAX][MAX];
int lookup_chain(int *p,int i,int j){
    int k,q=0;
    if(m[i][j]<INF)
        return m[i][j];
    if(i==j)
       m[i][j]=0;
    else{
        for(k=i;k<j;k++){
            q=lookup_chain(p,i,k)+lookup_chain(p,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(int i,int j){
    if(i==j)
        printf("A%d",i);
    else{
        printf("(");
        print(i,s[i][j]);
        print(s[i][j]+1,j);
        printf(")");
    }
}

int main(){
     int p[]={40,20,30,10,30};
    int i,j,n;
    n=sizeof(p)/sizeof(p[0]);
    for(i=0;i<n;i++)
        for(j=i;j<n;j++)
            m[i][j]=INF;
    printf("Scalar Multiplications: %d\n\n",lookup_chain(p,1,n-1));
    printf("Multiplication Order: ");
    print(1,n-1);
    return 0; 
}

Output: