You have a convex n-sided polygon where each vertex has an integer value. You are given an integer array values where values[i] is the value of the ith vertex in clockwise order. Polygon triangulation is a process where you divide a polygon into a s

minScoreTriangulation.js

/**
 * @param {number[]} values
 * @return {number}
 */
var minScoreTriangulation = function(values) {
    const n = values.length;

    // Create a 2D DP table initialized with 0s
    // dp[i][j] will store the minimum triangulation score for the subpolygon from vertex i to vertex j.
    const dp = Array.from ({ length: n }, () => Array(n).fill(0));

    // We consider all subpolygons of length 3 or more.
    for (let length = 3; length <= n; length++) {
        // i is the starting vertex of the subpolygon
        for (let i = 0; i <= n - length; i++) {
            // j is the ending vertex of the subpolygon
            const j = i + length - 1;

            // Initialize dp[i][j] to a large value so we can minimize it
            dp[i][j] = Infinity;

            // Try all possible third vertices k between i and j to form triangle (i, k, j)
            for (let k = i + 1; k < j; k++) {
                // Score of triangulating (i, k, j) plus the scores of triangulating the two resulting subpolygons
                const score = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];

                // Keep the minimum score found
                dp[i][j] = Math.min(dp[i][j], score);
            }
        }
    }

    // The final answer is the minimum score to triangulate the entire polygon from vertex 0 to n-1
    return dp[0][n - 1];
};