Matrix Chain Multiplication

Easy
0/40
profile
Contributed by
10 upvotes
Asked in companies
AdobeGrabSpringworks

Problem statement

You are given ‘N’ 2-D matrices and an array/list “ARR” of length ‘N + 1’ where the first ‘N’ integers denote the number of rows in the Matrices and the last element denotes the number of columns of the last matrix. For each matrix, the number of columns is equal to the number of rows of the next matrix. You are supposed to find the minimum number of multiplication operations that need to be performed to multiply all the given matrices.

Note : 
You don’t have to multiply the matrices, you only have to find the minimum number of multiplication operations.
For Example : 
ARR = {2, 4, 3, 2}

Here, we have three matrices with dimensions {2X4, 4X3, 3X2} which can be multiplied in the following ways:
a. If the order of multiplication is (2X4, 4X3)(3X2), then the total number of multiplication operations that need to be performed are: (2*4*3) + (2*3*2) = 36

b. If the order of multiplication is (2X4)(4X3, 3X2), then the total number of multiplication operations that need to be performed are  (2*4*2) + (4*3*2) = 40
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.

The first line of each test case contains a single integer ‘N’ denoting the number of the matrices.

The second line of each test case contains ‘N + 1’ single space-separated integers denoting where the first ‘N’ integers denote the number of rows in the Matrices and the last element denotes the number of columns of the last matrix.
Output Format : 
For each test case, print the minimum number of multiplication operations that need to be performed to multiply all the given matrices.

Print the output of each test case on a new line.
Note : 
You don’t need to print anything; It has already been taken care of.
Constraints : 
1 <= T <= 5
1 <= N <= 100
1 <= ARR[i] <= 10^2

Time Limit: 1 sec
Sample Input 1 :
2
4
2 4 3 2
5
1 2 4 1 3
Sample Output 1 :
36
13
Explanation For Sample Input 1 :
In the first test case, the minimum operations can be obtained by multiplying the matrices in the following order (2X4, 4X3)(3X2).


In the second test case, the minimum operations can be obtained by multiplying the matrices in the following order (1X2, (2X4, 4X1)),(1X3).
Sample Input 2 :
2
4
2 3 2 3
3
3 4 5
Sample Output 2 :
24
60
Hint

Can you try all possible orders of multiplying the matrices?

Approaches (3)
Recursive brute force

The idea is to use the recursion to try all the possible combinations of multiplying the matrices. After trying all the possible combinations we will take the minimum operations out of all the combinations.

 

For multiplying two matrices with dimensions (mXn) and (nXp), the number of operations required are m * n * p.

 

The steps are as follows :

 

  • Define a function minOperations(i, j), here ‘i’ denotes the i’th matrix and ‘j’ denotes the j’th matrix. This function will return the minimum number of multiplication operations needed to multiply all matrices from index ‘i’ to ‘j’.
  • The base case for this will be when ‘i’ is equal to ‘j’, we will return 0 in this case as we have only one matrix.
  • Otherwise, iterate from ‘i’ till ‘j’, let’s say our current index is ‘k’.
    • Recursively calculate the minimum number of operations for multiplying all matrices from ‘i’ to ‘k’ i.e minOperations(i,k) and all matrices from ‘k + 1’ to ‘j’ i.e. minOperations(k+1,j).
    • After multiplying all matrices from ‘i’ to ‘k’ and all matrices from ‘k + 1’ to ‘j’ we will be left with two matrices with dimensions (ARR[i - 1], ARR[k]) and (ARR[k], ARR[j]). The number of operations needed for multiplying these two matrices will be ARR[i - 1] * ARR[k] * ARR[j]. Hence we will add this value to the answer.
  • We will return the minimum out of all possibilities.
Time Complexity

O(4^N / (N^(3 / 2))), where ‘N’ is the number of matrices.

 

We are trying all possible combinations of multiplying the matrices, this approach has a recurrence of T(i, j)= SUM(T(i, k) * T(k+1, j) for all ‘k’ from ‘i’ to ‘j’. This recurrence simplifies down to  4^N / (N^(3/2) ) (using Catalan numbers). Thus, the overall time complexity is O(4^N / (N^(3 / 2))).

Space Complexity

O(N), where N is the number of matrices.

 

We are using recursion to try all possible ways of multiplying the matrices. The recursion stack grows maximum up to a size of ‘N’. Thus, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Matrix Chain Multiplication
Full screen
Console