Q24 Matrix Chain Multiplication | Practice | GeeksforGeeks

//{ Driver Code Starts
//Initial Template for Java

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

class GFG
{
    public static void main(String args[])throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());
        while(t-- > 0){
            int N = Integer.parseInt(in.readLine());
            String input_line[] = in.readLine().trim().split("\\s+");
            int arr[]= new int[N];
            for(int i = 0; i < N; i++)
                arr[i] = Integer.parseInt(input_line[i]);
            
            Solution ob = new Solution();
            System.out.println(ob.matrixMultiplication(N, arr));
        }
    }
}

// } Driver Code Ends


//User function Template for Java

class Solution{
    static int matrixMultiplication(int n, int arr[])
    {
        /* making a dp array for the gap strategy and to store answer of previous matrice
        multiplication
        1)travelling the gap diagonals and handling trivial cases for 0 and 1 diagnol
        2)handling for gap diagonals >= 2
        */
        
        int[][] dp = new int[n-1][n-1];
        
        //1
        for(int gap = 0 ; gap < n-1 ; gap++ ){
            
            
            for(int i =0 , j = gap ; j < n-1 ; i++ ,j++){
                
                if(gap == 0)
                dp[i][j] = 0;
                
                //i is first matrix , j is 2nd matrix
                else if(gap == 1)
                dp[i][j] = arr[i] * arr[j] * arr[j+1];
                
                //2
                else{
                    //k represents the cuts we are making from 0 to j-1
                    
                    int min = Integer.MAX_VALUE;
                    for(int k = i ; k < j ; k++){
                    //dp -> [i,k] = left half and [k+1,j] = right half
                    //arr -> i*k+1 = left half , k+1*j+1 = right half
                        int left = dp[i][k];
                        int right = dp[k+1][j];
                        int m = arr[i] * arr[k+1] * arr[j+1];
                        
                        min = Math.min(min , left + right + m);
                    }
                    dp[i][j] = min;
                }
            }
        }
        
        return dp[0][n-2];
    }
}