LeetCode Challenge Day 14 — 1039. Minimum Score Triangulation of Polygon

Hey folks

This is Day 14 of my LeetCode streak 🚀.
Today’s problem is 1039. Minimum Score Triangulation of Polygon — we’re given a convex polygon, and we need to split it into triangles such that the sum of triangle weights is minimized.

Each triangle’s weight is the product of its three vertices. Sounds like an optimization problem — and that’s where dynamic programming shines ✨.

📌 Problem Statement

You are given an integer array values of length n where n >= 3, representing the vertices of a convex polygon in clockwise order.

You must triangulate the polygon into n-2 triangles. Each triangle’s score is the product of the three vertex values.

Return the minimum possible total score achieved by triangulating the polygon.

Example

• Input: values = [1,3,1,4,1,5]
  Output: 13

Explanation: The optimal triangulation minimizes the sum of triangle scores.

Constraints

• 3 <= values.length <= 50

• 1 <= values[i] <= 100

💡 Intuition

Since the polygon is convex, any triangulation is valid.
But we want the one with the minimum score.

Brute force would try all triangulations — but that explodes exponentially.
Instead, we can use dynamic programming:

• Define dp[i][j] as the minimum triangulation score of the sub-polygon from vertex i to j.

• If fewer than 3 vertices, no triangle → cost is 0.

• Otherwise, try all possible third vertices k between i and j.

• The cost =

  dp[i][k]+dp[k][j]+values[i]×values[k]×values[j]dp[i][k] + dp[k][j] + values[i] \times values[k] \times values[j]dp[i][k]+dp[k][j]+values[i]×values[k]×values[j]

Take the minimum across all choices of k.

🔑 Approach

1. Initialize a 2D DP table dp[n][n] with zeros.

2. Iterate by interval length (len = 3 → n).

3. For each (i, j) interval, compute the best triangulation by trying all possible k.

4. Store the minimum in dp[i][j].

5. Answer is dp[0][n-1].

⏱️ Complexity Analysis

• Time complexity: O(n³) — for each pair (i, j), we try all k.

• Space complexity: O(n²) — DP table of size n × n.

🧑‍💻 Code (JavaScript)

/**
 * @param {number[]} values
 * @return {number}
 */
var minScoreTriangulation = function(values) {
  const n = values.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  for (let len = 3; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      let best = Infinity;
      for (let k = i + 1; k < j; k++) {
        const cost = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
        best = Math.min(best, cost);
      }
      dp[i][j] = best;
    }
  }
  return dp[0][n - 1];
};

// ✅ Quick tests
console.log(minScoreTriangulation([1,3,1,4,1,5])); // 13
console.log(minScoreTriangulation([3,7,4,5])); // 144

🧪 Edge Cases

• Minimum polygon (3 vertices) → just one triangle.

• All values = 1 → cost is n-2.

• Large n (50) → O(n³) is still fine.

🎥 Reflections

This problem is a classic DP on intervals.
At first, it feels overwhelming to try all triangulations, but breaking it into smaller sub-polygons makes it very manageable.

That’s it for Day 14 of my LeetCode journey!
On to the next challenge 🔥

Happy Coding 👨‍💻