34. Matrix Chain Multiplication Recursive

34 .Matrix Chain Multiplication Recursive
Video Link : https://youtu.be/kMK148J9qEE
GFG Problem Link : https://practice.geeksforgeeks.org/problems/matrix-chain-multiplication0303/1

Recursive Solution ; 

                  ------->>>>>>>>>>>------------>>>>>>>>>>>>________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 solve(int arr[], int i,int j)
 {
    // base condition 
     if(i>= j ){
         return 0;
     }
     
   //  to store the minimun answer
     int mn= INT_MAX;
     
     
     for(int k=i;k<j;k++)
     {
         //store the temporary potential answer
         
         int temp= solve(arr,i,k) + solve(arr, k+1,j) + arr[i-1] * arr[k] * arr[j] ; 
         
         mn= min(temp, mn);
         
         
     }
     
     return mn; 
     
 }

    int matrixMultiplication(int N, int arr[])
    {
        // code here
        
        int i=1,j=N-1;
        
        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