Minimum Score Triangulation of Polygon: Interval DP on Shapes

You have a convex polygon with n vertices, where each vertex has an integer value given by values[i]. You need to triangulate the polygon into n - 2 non-overlapping triangles. The score of each triangle is the product of the values at its three vertices. Return the minimum possible total score of all the triangles in a valid triangulation.

This is 1039. Minimum Score Triangulation of Polygon, and it is a clean example of interval DP applied to geometric decomposition. If you have seen Burst Balloons or Matrix Chain Multiplication, the pattern here will feel familiar. The key idea is to fix an edge and ask which vertex completes the triangle.

Why greedy fails

You might think about greedily picking the triangle with the smallest product at each step. But removing a triangle changes which triangles are available next. The locally cheapest triangle might force you into expensive choices later. The dependencies between choices mean you need to explore all valid triangulations, and DP gives you a way to do that efficiently.

The interval DP approach

Think about any edge of the polygon, say the edge between vertex i and vertex j. In a valid triangulation, some triangle must use this edge. That triangle is formed by picking a third vertex k strictly between i and j (going around the polygon). The triangle (i, k, j) splits the sub-polygon from i to j into two smaller sub-polygons: one from i to k, and one from k to j. Those two sub-polygons are completely independent, so you can solve them separately.

Define dp[i][j] as the minimum score to triangulate the sub-polygon consisting of vertices i, i+1, ..., j (in order around the polygon).

The recurrence is:

dp[i][j] = min over k in (i+1 .. j-1) of:
    dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]

The base case is dp[i][i+1] = 0. Two adjacent vertices form an edge, not a triangle, so there is nothing to triangulate and the cost is zero.

You fill the table by increasing interval length (the gap between j and i). When j - i equals 2, there is exactly one triangle and one choice of k. When the gap is larger, you try all valid k values and take the minimum. The final answer is dp[0][n-1].

Why this works

For any sub-polygon from vertex i to vertex j, the edge (i, j) must belong to exactly one triangle. That triangle uses some vertex k between i and j. Once you commit to that triangle, the remaining polygon splits into two independent pieces along the edges (i, k) and (k, j). The cost of the chosen triangle is values[i] * values[k] * values[j], and the costs of the two sub-polygons are dp[i][k] and dp[k][j]. Since the sub-polygons do not share any diagonals, their triangulations are independent. This is exactly the optimal substructure that makes DP work.

Python solution

def minScoreTriangulation(values: list[int]) -> int:
    n = len(values)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            dp[i][j] = float("inf")
            for k in range(i + 1, j):
                dp[i][j] = min(
                    dp[i][j],
                    dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]
                )
    return dp[0][n - 1]

The outer loop iterates over interval lengths from 2 up to n - 1. For each pair (i, j), you try every vertex k between them as the apex of the triangle on edge (i, j). The minimum across all choices of k becomes dp[i][j].

Step-by-step walkthrough

Complexity analysis

Time: O(n^3). There are O(n^2) sub-intervals (i, j). For each one, you try up to O(n) values of k. With n up to 50, this is at most 125,000 operations.

Space: O(n^2). The DP table has one entry per pair of vertices, so n * n entries total.

The building blocks

Interval DP (decompose by choosing a split point). The core pattern is: fix the endpoints of an interval, try every interior point as a "split," and combine the costs of the two resulting sub-intervals plus the cost of the current choice. This same structure appears in Matrix Chain Multiplication, Burst Balloons, and Optimal Binary Search Tree. Whenever you see a problem where a sequence or polygon must be partitioned and the cost depends on the partition boundaries, interval DP is the tool. The key is identifying what to "fix" (an edge, a boundary) and what to "choose" (the split vertex).

Polygon triangulation as subproblem decomposition. Triangulating a convex polygon is a geometric version of the interval DP pattern. Each triangle you add removes a vertex from the polygon and splits the remaining shape into independent sub-polygons. The insight that a convex polygon with vertices listed in order maps directly to an interval [i, j] makes the geometric problem reducible to a 1D interval problem. This mapping from geometry to intervals is a useful mental model for any problem where a shape must be recursively subdivided.

Edge cases to watch for

• Triangle (n = 3): Only one possible triangulation. dp[0][2] = values[0] * values[1] * values[2]. No choices to make.
• All values equal: Every triangulation has the same score, so any split is optimal.
• One vertex has value 1: Triangles involving this vertex have smaller products. The optimal triangulation tends to "fan out" from the vertex with value 1, making it a shared vertex in as many triangles as possible.
• n = 4 (quadrilateral): Two possible triangulations. The DP considers both diagonals and picks the cheaper one.

From understanding to recall

The connection between polygon triangulation and interval DP is the kind of insight that is easy to follow when explained but hard to regenerate from scratch. Under time pressure, you need to instinctively see a convex polygon as an interval of vertices and know that fixing an edge and choosing a pivot vertex gives you independent sub-problems.

Spaced repetition locks this in. After a few rounds of re-deriving the recurrence from the polygon picture, the mapping becomes automatic. You see "triangulate" and your hands write the triple nested loop. The interval DP pattern and the geometric decomposition insight are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems.

Related posts

• Burst Balloons - Same interval DP pattern with products
• Minimum Cost to Merge Stones - Another interval DP problem
• Largest Sum of Averages - Partition DP with similar subproblem structure