Matrix chain multiplication in C++

Given a sequence of matrixes, we have to decide the order of multiplication of matrices which would require the minimum cost. We don’t need to find the multiplication result but the order of matrices in which they need to be multiplied. Matrix chain multiplication in C++ is an interesting problem. The matrix multiplication is associative,  thus we have various ways to multiply. For example-

suppose A is a 15 × 20 matrix, B is a 20 × 5 matrix, and C is a 5 × 40 matrix. Then,

    (AB)C = (15×20×5) + (20×5×40) = 1500 + 4000 = 5500 operations
    A(BC) = (20×5×40) + (15×20×40) = 4000 + 12000 = 16000 operations.

Clearly, the first one gives us fewer operations. We need to find the minimum one among all.

ABCD---->((AB)C)D----->(((A)B)C)D----->(AB)(CD)----->A((BC)D)

These above are some of the ways of multiplication, though there can be many.

Matrix chain multiplication in C++

Let us solve this problem using dynamic programming. Let us take one table M. In the tabulation method we will follow the bottom-up approach.

A(5*4) B(4*6) C(6*2) D (2*7)

Let us start filling the table now.

1. m[1,1] tells us about the operation of multiplying matrix A with itself which will be 0. So fill all the m[i,i] as 0.
2. m[1,2] We are multiplying two matrices A and B. Operations will be 5*4*6=120.
3. m[2,3] We are multiplying B and C now. Operations will be 4*6*2=48
4. m[3,4] can be also filled in the same way.

5. Now, m[1,3]- We are considering three matrices A, B, and C. Now there are two ways to do this.

   A(BC) 

   m[1,1]+m[2,3]+5*4*2=0+48+40=88

   (AB)C 

   m[1,2]+m[3,3]+5*6*2=120+0+60=180                                                                                                                                                               
   We select the minimum from above and fill it in the table.

6. Similarly, m[2,4] can be found out.

7. m[1,4] can be deduced as:                                        
        m[1,4]=min(m[1,1]+m[2,4]+5*4*7,m[1,2]+m[3,4]+5*6*7,m[1,3]+m[4,4]+5*2*7)   
        m[1,4]=min(0+104+140,120+84+210,88+0+70)   
        m[1,4]=158

8. So, the formula which we deduced from our observations above is:

m[i,j]=min(m[i,k]+m[k+1,j]+d(i-1)*d(k)*d(j))(d represents order of matrix)

Here, is the table of operations:

Here, is the code:

#include<bits/stdc++.h>
using namespace std;


int MatrixChainOrder(int p[], int n) 
{ 
  int m[n][n]; 

  int i, j, k, L, q; 
 
  for (i=1; i<n; i++) 
    m[i][i] = 0; 

  for (L=2; L<n; L++) //filling half table only
  { 
    for (i=1; i<n-L+1; i++) 
    { 
      j = i+L-1; 
      m[i][j] = INT_MAX; 
      for (k=i; k<=j-1; k++) 
      { 
        q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; 
        if (q < m[i][j]) 
          m[i][j] = q; 
      } 
    } 
  } 

  return m[1][n-1]; 
} 

int main() 
{ 
  int arr[] = {5,4,6,2,7}; 
  int size = 5; 
    cout<<MatrixChainOrder(arr,size)<<" operations";

  
} 

Output:

158 operations

Time complexity:o(n^3)

Also, refer to:

Count the number of occurrences in a linked list in C++

Thank you! please comment on suggestions