Matrix Chain Multiplication

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.

Let’s have a look at the recursion tree of the previous approach.

We see that we are solving the same subproblem more than once.

The idea is to use dynamic programming to store the results of a subproblem so that we don’t solve the same subproblem more than once.

The steps are as follows :

• Let’s declare a 2-D matrix “dp” to store the results of a subproblem. Let’s define dp[i][j] as the minimum multiplication operations required to multiply all matrices from index ‘i’ to ‘j’. Initially, all elements of the dp matrix are -1.
• 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 operations needed to multiply all matrices from index ‘i’ to ‘j’.
• The base case for this function will be when ‘i’ is equal to ‘j’, we will return 0 in this case as we have only one matrix.
• If dp[i][j] is not equal to -1, then we will return the value of dp[i][j] because we have already calculated the minimum operations needed to multiply all matrices from index ‘i’ to ‘j’.
• 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’ by calling minOperations(i, k)  and the minimum number of operations for multiplying all matrices from ‘k + 1’ to ‘j’ by calling 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.
• Store the minimum number of operations in dp[i][j] and return dp[i][j].

The idea is to use dynamic programming to store the results of a subproblem and then use the stored results to solve other subproblems.

We will iterate over the length of subarrays, let’s say the current length is “len” and in one iteration we will solve the problem for all subarrays of size “len” by using the previously-stored results of subarrays having a length less than “len”.

The steps are as follows:

• Let’s define a 2-D matrix “dp” to store the results of a subproblem. Let’s define dp[i][j] as the minimum multiplication operations required to multiply all matrices from index ‘i’ to ‘j’.
• Iterate through the”dp” array and initialize dp[i][i ] =0 for all ‘i’ in [0, n), because we need 0 operations for multiplying one single matrix.
• Iterate over the length of the subarrays starting from 2 and going till ‘N’, let’s say the current length is “len”.
  • Iterate over all subarrays having a length equal to “len”, let’s say the current subarray is from index ‘i’ to ‘j’.
    • Iterate from ‘i’ to ‘j - 1’, let’s say the current index is ‘k’.
    • Look up the dp table to calculate the number of operations required to multiply all matrices from ‘i’ to ‘k’( i.e. dp[i][k]) and all matrices from ‘k + 1’ to ‘j’(i.e. dp[k + 1][j]), let’s say this value is “operations”.
    • 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 “operations”.
    • If the value of dp[i][j] is greater than “operations” then update dp[i][j] to “operations”.
• The value of dp[1][N - 1] will store the minimum multiplication operations needed to multiply all the given matrices, hence we will return dp[1][N - 1].