How to perform Matrix Chain Multiplication

// TOP DOWN APPROACH 

// BOARD INFINITY 

#include<bits/stdc++.h>
using namespace std;
// Function to find the minimum number of Multiplication
//  steps required in multiplying a chain of n matrices.

int MatrixChainMultiplication(int mat[],int low, int high){
    // If we are left with one matrix then
    // we don't need any multiplication steps.
    if(low==high)
        return 0;
   
    // Initializing minCost with very
    // large value.
    int minCost=INT_MAX;
   
    // Iterating from low to high - 1
    for(int k=low;k<high;k++){
        /*
        Cost = Cost of Multiplying chain on left side +
                Cost of Multiplying chain on right side +
                Cost of Multiplying matrix obtained from left
                and right side.
        */
        int cost=MatrixChainMultiplication(mat, low, k)+
            MatrixChainMultiplication(mat, k+1, high)+
            mat[low-1]*mat[k]*mat[high];
       
        // If the above cost is less than
        // minCost find so far then update minCost.
        if(cost<minCost)
            minCost=cost;
    }
    // Returning the minCost
    return minCost;
}
// Main Function
int main(){
    // This matrix chain of length 5 represents
    // 4 matrices of dimensions as follows -
    // 2*4, 4*6, 6*8, and 8*6.
    int mat[]={2, 4, 6, 8, 6};
    int n=sizeof(mat)/sizeof(mat[0]);

    cout<<"Minimum number of steps are - ";
    cout<<MatrixChainMultiplication(mat, 1, n-1);
    return 0;
}

// BOTTOM UP APPROACH 

// BOARD INFINITY

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

// Function to find the minimum number of Multiplication
//  steps required in multiplying chain of n matrices.
int MatrixChainMultiplication(int mat[],int n){
    // Making 2d DP array of dimensions
    // (n-1)*(n-1)
    int dp[n-1][n-1];
   
    // Iterating while gap between first
    // length vary from 0 to n-1.
    for(int gap=0;gap<n-1;gap++){
        // Starting i from 0 and j=gap.
        // Iterating till j<n-1.
        for(int i=0,j=gap;j<n-1;i++,j++){
            // If gap is 0 (single matrix)
            // then assigning 0 to dp[i][j].
            if(gap==0)
                dp[i][j]=0;
            // Else if the gap is (2 matrices)
            // i.e. only once choice (mat1*mat2)
            else if(gap==1){
                dp[i][j]=mat[i]*mat[j]*mat[j+1];
            }
            // Else if gap>1, then we need to
            // find the optimal method.
            else{
                // Initializing minCost with very large value.
                int minCost=INT_MAX;
               
                // Iterating from k=i to
                // k = j-1 and finding cost.
                /*
                Cost = Cost of Multiplying chain on left side +
                        Cost of Multiplying chain on right side +
                        Cost of Multiplying matrix obtained from left
                        and right side.
                */
                for(int k=i;k<j;k++){
                    int leftCost=dp[i][k];
                    int rightCost=dp[k+1][j];
                    int thisCost=mat[i]*mat[k+1]*mat[j+1];
                   
                    minCost=min(minCost,leftCost
                            +rightCost+thisCost);
                }
                // Assigning minCost find to dp[i][j].
                dp[i][j]=minCost;
            }
        }
    }
    // Returning dp[0][n-2].
    return dp[0][n-2];
}
// Main Function
int main(){
    // This matrix chain of length 5 represents
    // 4 matrices of dimensions as follows -
    // 2*4, 4*6, 6*8, and 8*6.
    int mat[]={2, 4, 6, 8, 6};
    int n=sizeof(mat)/sizeof(mat[0]);
   
    cout<<"Minimum number of steps are - ";
    cout<<MatrixChainMultiplication(mat, n);
    return 0;
}