public class MatrixChainMultiplication {

    public int findCost(int arr[]){
        int temp[][] = new int[arr.length][arr.length];
        int q = 0;
        /*for(int l=2; l < arr.length; l++){
            for(int i=0; i < arr.length - l; i++){
                int j = i + l;
                temp[i][j] = 1000000;
                for(int k=i+1; k < j; k++){
                    q = temp[i][k] + temp[k][j] + arr[i]*arr[k]*arr[j];
                    if(q < temp[i][j]){
                        temp[i][j] = q;
                    }
                }
            }
        }*/
        
        int n = arr.length;
        int l = 0;
        for (int i = 0; i < n-2; i++) {
        	l++;
        	for (int j = 1; j < n-l; j++) {
        		temp[j][j+l] = 1000000;
        		for (int k = j; k < j+l; k++) {
        			q = temp[j][k] + temp[k+1][j+l] + arr[j]*arr[k]*arr[j+l];
        			if (q < temp[j][j+l])
        				temp[j][j+l] = q;
        		}
        	}
        }
        
        for (int i = 0; i < arr.length; i++) {
        	for (int j = 0; j < arr.length; j++)
        		System.out.print(temp[i][j] + " ");
        	System.out.println();
        }
        
        return temp[0][arr.length-1];
    }
    
    public static void main(String args[]){
    	MatrixChainMultiplication mmc = new MatrixChainMultiplication();
        int arr[] = {2,3,6,4,5};
        int cost = mmc.findCost(arr);
        System.out.print(cost);
    }
}