Matrix Chain Multiplication Problem

This is a C++ Program that Solves Matrix Chain Multiplication Problem using Dynamic Programming technique.

Problem Description

Given order of n matrices, find the minimum multiplication operations required for multiply n matrices.

Required condition for multiplying two matrices
If we have two matrix A of order a*b and matrix B of order c*d. In the product A*B, matrix A is called pre-multiplier and B is called the post-multiplier. A and B can be multiplied if b=c. And the order of the resulting matrix will be a*d.

In general, the number of columns of pre-multiplier matrix should be equal to number of rows of post-multiplier matrix.

Multiplication operations performed for multiplying two matrices
In the above example, the number of multiplication operations required for multiplying matrix A and B, will be a*b*d.

Now, suppose we have three matrices as follows –
matrix A of order a*b
matrix B of order b*c
matrix C of order c*d

We have to find the product A*B*C. This can be done in two ways mentioned below –
((A*B)*C) – first multiplying A and B and then multiplying the resulting matrix with c
This will cost a*b*c + a*c*d multiplication operations

(A*(B*C)) – first multiplying B and C and then multiplying A with the resulting matrix
This will cost a*b*d + b*c*d multiplication operations

So, a given matrix chain be multiplied in various ways. The goal of the problem is to find the least number of operations required to find the product of the matrix chain.

Note: Join free Sanfoundry classes at Telegram or Youtube

If in the above explanation a=3, b=9, c=7, d=2
((A*B)*C) will take 231 multiplication operations
(A*(B*C)) will take 180 multiplication operations

So, the preferred way of multiplication will be (A*(B*C)).

Problem Solution

This problem can be solved using Dynamic Programming. First we will compute results for sub-chains of the original chain and store these results in a 2-D array. Then we will use these results to compute results for larger chains.

Time Complexity of this solution is O(n^3).

Program/Source Code

Here is source code of the C++ Program to Solve Matrix Chain Multiplication Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
#include<climits>
```
```
using namespace std;
```
```
 
```
```
int matrixChain(int n, int order[])
```
```
{
```
```
    int i,j,k;
```
```
    int tempValue;
```
```
 
```
```
    int dp[n+1][n+1];
```
```
 
```

    //dp[i][j] denotes the minimum number of multiplication operations required to compute the matrix chain product of chain of matrix i to matrix j

```
 
```
```
    //initialization
```

    //No multiplication operations will be done if the chain consists of a single matrix

```
    for(i=1;i<=n;i++)
```
```
    {
```
```
        dp[i][i]=0;
```
```
    }
```
```
 
```

    //first we will calculate min. operations for a all chains of size of 2, then for all chains of size 3 and finally for the original chain ie., of size n

```
    for(int size=2;size<=n;size++)
```
```
    {
```

        //i is the first matrix of the chain

```
        for(i=1;i<=(n-size+1);i++)
```
```
        {
```

            //j is the first matrix of the chain

```
            j=i+size-1;
```
```
 
```

            //now, calculate the min. multiplications required to compute product of the chain with matrices i, i+1,...,j

            //First initialize the result to infinity and then replace if lesser results are obtained

```
            dp[i][j]=INT_MAX;
```
```
 
```

            //now, divide the chain of matrices i....j into two sub-chains i...k and k+1...j and use the already computed results of these sub-chains to compute the result of original chain

```
            for(k=i;k<j;k++)
```
```
            {
```

                tempValue=dp[i][k]+dp[k+1][j]+order[i-1]*order[k]*order[j];

```
 
```

                //if tempValue is lesser than the current value of dp[i][j], replace it

```
                if(tempValue<dp[i][j])
```
```
                {
```
```
                    dp[i][j]=tempValue;
```
```
                }
```
```
            }
```
```
 
```
```
        }
```
```
 
```
```
    }
```
```
 
```

    //return the min. multiplication operations for the original matrix

```
    return dp[1][n];
```
```
 
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i,j;
```
```
    int n;
```
```
 
```

    cout<<"Enter the number of matrices in the chain(greater than 1)  ";

```
    cin>>n;
```
```
 
```
```
    int order[n+1];
```
```
 
```

    //order of matrix i will be given by order[i-1]*order[i]

    cout<<"Enter the order array of the matrix chain ("<<n+1<<" elements)"<<endl;

```
    for(i=0;i<=n;i++)
```
```
    {
```
```
        cin>>order[i];
```
```
    }
```
```
 
```

    cout<<"The minimum number of multiplication operations required to multiply the matrix chain is "<<matrixChain(n,order);

```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the number of matrices in the chain and order of each matrix in the chain. We pass these values to the function matrixChain as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases

 
Case-1:
$ g++ matrix_chain.cpp
$ ./a.out
Enter the number of matrices in the chain(greater than 1)  3
Enter the order array of the matrix chain (4 elements)
3
9
7
2
The minimum number of multiplication operations required to multiply the matrix chain is 180

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

« Prev - Optimal Strategy for a Game using Dynamic Programming

» Next - Longest Common Subsequence using Dynamic Programming

Related Posts:

Recommended Articles: