LeetCode 1039: Minimum Score Triangulation of Polygon

Problem Restatement

We have a convex polygon with n vertices labeled 0 to n - 1.

Each vertex has a value given in values[i].

We triangulate the polygon into n - 2 triangles. For each triangle with vertices i, j, k, the score is values[i] * values[j] * values[k].

We need to return the minimum total score over all possible triangulations.

The official constraints state that n == values.length, 3 <= n <= 50, and 1 <= values[i] <= 100.

Input and Output

Function shape:

def minScoreTriangulation(values: list[int]) -> int:
    ...

Examples

Example 1:

values = [1, 2, 3]

Only one triangulation: triangle (0, 1, 2). Score = 1 * 2 * 3 = 6.

Answer:

6

Example 2:

values = [3, 7, 4, 5]

Two triangulations:

• Diagonals (0,2): triangles (0,1,2) and (0,2,3). Score = 84 + 60 = 144.
• Diagonals (1,3): triangles (0,1,3) and (1,2,3). Score = 105 + 140 = 245.

Answer:

144

Key Insight

This is an interval DP problem.

Fix vertex 0 (or any vertex). Every triangle in the triangulation includes exactly two boundary vertices of the current sub-polygon. The third vertex splits the problem into two subproblems.

Let dp[i][j] = minimum score to triangulate the sub-polygon with vertices i, i+1, ..., j.

For each possible “apex” vertex k between i and j:

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

Correctness

Fixing edge (i, j) and trying all apex vertices k between them covers every valid triangle that uses edge (i, j). The recurrence combines the two sub-polygons on either side of the diagonal (i, k) and (k, j).

Base case: any sub-polygon with fewer than 3 vertices has score 0.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Complexity

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

class Solution:
    def minScoreTriangulation(self, 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] + values[i] * values[k] * values[j] + dp[k][j])

        return dp[0][n - 1]

Testing

def run_tests():
    s = Solution()

    assert s.minScoreTriangulation([1, 2, 3]) == 6
    assert s.minScoreTriangulation([3, 7, 4, 5]) == 144
    assert s.minScoreTriangulation([1, 3, 1, 4, 1, 5]) == 13

    print("all tests passed")

run_tests()