Q-49 Matrix Chain Multiplication - Coding Ninjas

import java.util.* ;
import java.io.*; 

public class Solution {
	public static int matrixMultiplication(int[] arr , int n) {
		
		// return solve(1 , n-1 , arr , new Integer[n][n]);

		//tabulization 
		int[][] dp = new int[n][n];
		for(int i = n-1 ;i >= 1 ; i--){
			//i will be always to the left of j
			for(int j = i+1 ;j < n ; j++){
				if(i == j)//base case
				dp[i][j] = 0;

				else {
					int mini = (int)1e9;   

		     
					for(int k = i ;k < j ; k++){
						int steps = arr[i-1]*arr[k]*arr[j] + dp[i][k] + dp[k+1][j];
						
						if(steps < mini)mini = steps;
					}
					
					dp[i][j] = mini;
				}
			}
		}

		return dp[1][n-1];
	}

	//Recursion->Exponential Memo-> n*n*n | sc- n*n + n+n
	//we call for(1,n-1)and tell it give its 2 minimum multiplication matrix 
	//then we add the multiplication to multiply those matrix
	public static int solve( int i , int j , int[] arr , Integer[][] dp){
        //if only 1 matrix
		if(i == j) return 0;
        
		if(dp[i][j] != null)
		return dp[i][j];

		int mini = (int)1e9;   

		     
        for(int k = i ;k < j ; k++){
            int steps = arr[i-1]*arr[k]*arr[j] + solve(i,k,arr , dp) + solve(k+1 , j , arr , dp);
            
            if(steps < mini)mini = steps;
        }
        
        return dp[i][j] = mini;
    }
}