Problem Statement

Given a sequence of matrices, find the most efficient way to multiply these matrices together. The efficient way is the one that involves the least number of multiplications. The dimensions of the matrices are given in an array arr[] of size N (such that N = number of matrices + 1) where the ith matrix has the dimensions (arr[i-1] x arr[i]).

Example 1:

Input: N = 5
arr = {40, 20, 30, 10, 30}
Output: 26000
Explaination: There are 4 matrices of dimension
40x20, 20x30, 30x10, 10x30. Say the matrices are
named as A, B, C, D. The efficient way is
(A*(B*C))*D. The number of operations are 20*30*10
+ 40*20*10 + 40*10*30 = 26000.

Problem Link

Matrix Chain Multiplication | DP-8 - GeeksforGeeks

Reference Videos

Using Memoization (Top Down DP)

                                                                Using Memoization (Top Down DP)

Using Bottom Up DP

                                                                          Using Bottom Up DP

Code

//Using Memoization

class Solution{
   int dp[101][101];
public:
    int topdownDP(int i,int j,int arr[]) {
        
        if(i>=j)
        return dp[i][j] = 0;
        
        if(dp[i][j]!=-1)
        return dp[i][j];
        
        dp[i][j] = INT_MAX;
        for(int k=i;k<j;k++)
        {
            dp[i][j] = min(dp[i][j],topdownDP(i,k,arr)+topdownDP(k+1,j,arr)+arr[i-1]*arr[j]*arr[k]);
        }
        return dp[i][j];
    }
    int matrixMultiplication(int N, int arr[])
    {
       memset(dp,-1,sizeof(dp));
       
      return **topdownDP(1,N-1,arr);**
       
      
    }
};

//Using Bottom-Up DP

class Solution{

public:
   
    int matrixMultiplication(int N, int arr[])
    {
       **vector<vector<int>> dp(N,vector<int>(N));**
       
       for(int gap=0;gap<N;gap++) {
           for(int i=0,j=gap;j<N;j++,i++) {
               
               if(gap==0||i==0) 
               dp[i][i] = 0;
               
               else {
                   dp[i][j] = INT_MAX;
                
                   for(int k=i;k<j;k++)
                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+arr[i-1]*arr[j]*arr[k]);
                    
               }
        }
     }
   
      **return dp[1][N-1];**
       
      
    }
};

Time Complexity : O(n^3), Space Complexity : O(n^2)