Untitled

import java.util.Arrays;

public class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        // Create a memoization table and initialize it with -1 (indicating not computed)
        int[][] memo = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], -1);
        }
        // Calculate the minimum score for the full polygon (from index 0 to n-1)
        return solve(0, n - 1, values, memo);
    }
    
    private int solve(int i, int j, int[] values, int[][] memo) {
        // Base case: if the subpolygon has fewer than 3 vertices, no triangle can be formed.
        if (j - i < 2) {
            return 0;
        }
        
        // Return the result if it has been computed before.
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        
        int minCost = Integer.MAX_VALUE;
        // Try every possible intermediate vertex 'k' between i and j
        for (int k = i + 1; k < j; k++) {
            // Compute the cost for forming the triangle (i, k, j)
            // plus the cost of triangulating the left and right subpolygons.
            int cost = solve(i, k, values, memo) 
                     + solve(k, j, values, memo) 
                     + values[i] * values[k] * values[j];
            minCost = Math.min(minCost, cost);
        }
        
        // Store the computed minimum cost in the memo table.
        memo[i][j] = minCost;
        return minCost;
    }
}