Minimum Score Triangulation of Polygon

Minimum Score Triangulation of Polygon

What is this problem about?

The Minimum Score Triangulation of Polygon problem gives you a convex polygon with n vertices where each vertex has a value. Triangulating the polygon means dividing it into n-2 triangles by drawing non-crossing diagonals. The score of a triangulation is the sum of products of the three vertex values for each triangle. Find the triangulation with the minimum score. This Minimum Score Triangulation of Polygon coding problem is a textbook interval dynamic programming challenge.

Why is this asked in interviews?

Uber, Microsoft, Meta, Amazon, and Google ask this because it requires recognizing the interval DP pattern in a geometric context. The connection between polygon triangulation and interval DP is non-obvious and tests deep algorithmic knowledge. The array and dynamic programming interview pattern is showcased here in a non-standard guise that distinguishes strong candidates.

Algorithmic pattern used

The pattern is interval dynamic programming (DP). Define dp[i][j] as the minimum score to triangulate the polygon formed by vertices i through j. For each triangle formed with vertices i, k, j (where i < k < j), the cost is values[i] * values[k] * values[j] plus the cost of triangulating the sub-polygons [i..k] and [k..j]. Transition: dp[i][j] = min over k of (values[i]*values[k]*values[j] + dp[i][k] + dp[k][j]). Base case: dp[i][j] = 0 when j - i < 2.

Example explanation

Polygon with vertices [1, 2, 3, 4, 5]. The entire polygon dp[0][4] tries all k: 1, 2, 3. k=2: 135 + dp[0][2] + dp[2][4] = 15 + (123) + (345) = 15 + 6 + 60 = 81. k=1: 125 + dp[0][1] + dp[1][4] = 10 + 0 + ... Continue to find the minimum across all k values.

Common mistakes candidates make

• Confusing the base case (triangles with fewer than 3 vertices have zero cost).
• Wrong loop order — must fill smaller intervals before larger ones.
• Forgetting to include the cost of both sub-polygons recursively.
• Thinking polygon vertices wrap around — in this DP formulation they don't.

Interview preparation tip

Interval DP problems share a common template: define [i][j] as the optimal cost for a subproblem, enumerate a "split point" k, combine sub-solutions. Practice this template with matrix chain multiplication and burst balloons, which are structurally similar. Once you recognize "optimize over all ways to split a range," interval DP becomes second nature. Polygon triangulation is one of the most elegant applications of this pattern.