Matrix Chain Multiplication using Dynamic Programming

«
»

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

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

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.

Take Data Structure I Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

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).

advertisement
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.

  1. #include<iostream>
  2. #include<climits>
  3. using namespace std;
  4.  
  5. int matrixChain(int n, int order[])
  6. {
  7.     int i,j,k;
  8.     int tempValue;
  9.  
  10.     int dp[n+1][n+1];
  11.  
  12.     //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
  13.  
  14.     //initialization
  15.     //No multiplication operations will be done if the chain consists of a single matrix
  16.     for(i=1;i<=n;i++)
  17.     {
  18.         dp[i][i]=0;
  19.     }
  20.  
  21.     //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
  22.     for(int size=2;size<=n;size++)
  23.     {
  24.         //i is the first matrix of the chain
  25.         for(i=1;i<=(n-size+1);i++)
  26.         {
  27.             //j is the first matrix of the chain
  28.             j=i+size-1;
  29.  
  30.             //now, calculate the min. multiplications required to compute product of the chain with matrices i, i+1,...,j
  31.             //First initialize the result to infinity and then replace if lesser results are obtained
  32.             dp[i][j]=INT_MAX;
  33.  
  34.             //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
  35.             for(k=i;k<j;k++)
  36.             {
  37.                 tempValue=dp[i][k]+dp[k+1][j]+order[i-1]*order[k]*order[j];
  38.  
  39.                 //if tempValue is lesser than the current value of dp[i][j], replace it
  40.                 if(tempValue<dp[i][j])
  41.                 {
  42.                     dp[i][j]=tempValue;
  43.                 }
  44.             }
  45.  
  46.         }
  47.  
  48.     }
  49.  
  50.     //return the min. multiplication operations for the original matrix
  51.     return dp[1][n];
  52.  
  53. }
  54.  
  55. int main()
  56. {
  57.     int i,j;
  58.     int n;
  59.  
  60.     cout<<"Enter the number of matrices in the chain(greater than 1)  ";
  61.     cin>>n;
  62.  
  63.     int order[n+1];
  64.  
  65.     //order of matrix i will be given by order[i-1]*order[i]
  66.     cout<<"Enter the order array of the matrix chain ("<<n+1<<" elements)"<<endl;
  67.     for(i=0;i<=n;i++)
  68.     {
  69.         cin>>order[i];
  70.     }
  71.  
  72.     cout<<"The minimum number of multiplication operations required to multiply the matrix chain is "<<matrixChain(n,order);
  73.  
  74.     cout<<endl;
  75.     return 0;
  76. }
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.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.