class Solution {
    public int minScoreTriangulation(int[] values) {
        /*  question no 27 in notes of dp playlist , catalan number , gap 
        strategy and matrix chain multiplication are being used 

        1) make 2d dp array to store results of previous polygon 
        2)every cell denotes minimum score to make that polygon with that 
        many sides
        3) traversing the gap diagnols and handling trivial cases  0 , 1

        4) handling further gap diagonals through formula for left , right 
        and immediate triangle using gap strategy 2
        */

        int n = values.length;
        int[][] dp = new int[n][n];

        for(int gap = 0 ; gap < n ; gap ++){

            for(int i = 0 , j = gap ; j < n ; i++ , j++){

                if(gap == 0 )
                dp[i][j] = 0;
                
                else if(gap == 1)
                dp[i][j] = 0;

                //only 1 triangle can be formed with 3 points
                else if(gap == 2)
                dp[i][j] = values[i] * values[i+1] * values[i+2];

                else{
                    //4
                    int min = Integer.MAX_VALUE;
                    for(int k = i+1 ; k<= j-1 ; k++){
                        int left = dp[i][k];
                        int right = dp[k][j];
                        int triangle = values[i] * values[j] * values[k];

                        min = Math.min(min , left + right + triangle);
                    }

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

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