35 .Matrix chain multiplication Memoization

35 . Matrix chain multiplication Memoization
Video Link : https://youtu.be/9uUVFNOT3_Y
GFG Practice link : https://practice.geeksforgeeks.org/problems/matrix-chain-multiplication0303/1

                  ------->>>>>>>>>>>------------>>>>>>>>>>>>________CODE________<<<<<<<<<<<<------------<<<<<<<<<<<<<<<<<<<<<<<<<<<

//{ Driver Code Starts
// Initial Template for C++

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

// } Driver Code Ends
// User function Template for C++

class Solution{
public:

int dp[101][101];

 int solve(int arr[], int i,int j)
 {
     
     if(i>= j ){
         return 0;
     }
     
    //  check if value is already present 
    
     if(dp[i][j]!=-1){
         return dp[i][j];
     }
     
     int mn= INT_MAX;
     
     for(int k=i;k<j;k++)
     {
         
         int temp= solve(arr,i,k) + solve(arr, k+1,j) + arr[i-1] * arr[k] * arr[j] ; 
         
         mn= min(temp, mn);
         
         
     }
     
     // before returnin store the value of dp[i][j] to further repeatitive calls 
     return dp[i][j]= mn; 
    
  
     
 }

    int matrixMultiplication(int N, int arr[])
    {
        // code here
        
        int i=1,j=N-1;
        
        memset(dp,-1,sizeof(dp)) ; 
        
        int ans= solve(arr, i,j);
        
        return ans; 
        
    }
};

//{ Driver Code Starts.

int main(){
    int t;
    cin>>t;
    while(t--){
        int N;
        cin>>N;
        int arr[N];
        for(int i = 0;i < N;i++)
            cin>>arr[i];
        
        Solution ob;
        cout<<ob.matrixMultiplication(N, arr)<<endl;
    }
    return 0;
}
// } Driver Code Ends