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; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter