MatrixChainMultiplication.java

// Memoization
publicclassSolution {
publicstaticintmatrixMultiplication(int[] arr , intN) {
if(N < 3) return0;

int[][] dp = newint[N][N]; 
for(inti = 0; i < N; i++)
for(intj = 0; j < N; j++)
dp[i][j] = -1;

returnpartition(1, N-1, arr, dp);
 }

privatestaticintpartition(inti, intj, int[] arr, int[][] dp) {
if(i == j) return0;

if(dp[i][j] != -1) returndp[i][j];

intmin = Integer.MAX_VALUE;

for(intk = i; k < j; k++) {
intcurr = (arr[i-1] * arr[k] * arr[j]) + 
partition(i, k, arr, dp) + partition(k+1, j, arr, dp);
min = Math.min(min, curr);
 }

returndp[i][j] = min;
 }
}

// Tabulation
publicclassSolution {
publicstaticintmatrixMultiplication(int[] arr , intN) {
if(N < 3) return0;

int[][] dp = newint[N][N]; 

for(inti = N-1; i > 0; i--) {
for(intj = i+1; j < N; j++) {
if(i == j) continue;

intmin = (int) 1e9;
for(intk = i; k < j; k++) {
min = Math.min(min, (arr[i-1] * arr[k] * arr[j]) + 
dp[i][k] + dp[k+1][j]);
 }

dp[i][j] = min;
 }
 }

returndp[1][N-1];
 }
}