Accepted Code for MCM

PROBLEM LINK: https://www.geeksforgeeks.org/problems/matrix-chain-multiplication0303/0



class Solution{
public:
    long long t[105][105];
    long long  mxm(int arr[],int i,int j){
        if(i>=j){
            return 0;
        }
        if(t[i][j]!=-1){
            return t[i][j];
        }
        long long mn=INT_MAX;
        for(int k=i;k<=j-1;k++){
            long long left,right;
            if(t[i][k]!=-1){
                left=t[i][k];
            }
            else{
                left=mxm(arr,i,k);
                t[i][k]=left;
            }
            if(t[k+1][j]!=-1){
                right=t[k+1][j];
            }
            else{
                right=mxm(arr,k+1,j);
                t[k+1][j]=right;
            }
            long long temp=left+right+(arr[i-1]*arr[k]*arr[j]);
            mn=min(temp,mn);
        }
        t[i][j]=mn;
        return mn;
    }
    int matrixMultiplication(int N, int arr[])
    {
        memset(t,-1,sizeof(t));
        int ans=mxm(arr,1,N-1);
        return ans;
    }
};