1039. Minimum Score Triangulation of Polygon

Link

Solution

  public int minScoreTriangulation(int[] A) {
        int N = A.length;
        int[][] dp = new int[N][N];
        
        for(int d = 2; d < N; d++){
            for(int i = 0; i+d < N; i++){
                int j = i + d;
                dp[i][j] = Integer.MAX_VALUE;
                for(int k = i+1; k < j; k++){
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + A[i]*A[j]*A[k]); 
                    //pick 3 points i, j, k to form a tangular and seprerte the main problem
                }
            }
        }
        return dp[0][N-1];
        
    }