#1039

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Score Triangulation of Polygon

Compute the minimum total score to triangulate a convex polygon using state transition dynamic programming on vertex values.

array dynamic programming

Problem Statement

Given a convex polygon with n vertices, each labeled with an integer from the array values in clockwise order, your task is to divide the polygon into n-2 triangles. Each triangle must use vertices from the original polygon, and no other shapes are allowed. The weight of a triangle is defined as the product of its three vertices.

Compute the minimum total score of the polygon triangulation by summing the weights of all triangles formed. Return this minimal sum. Constraints include 3 <= n <= 50 and 1 <= values[i] <= 100.

Examples

Example 1

Input: values = [1,2,3]

Output: 6

The polygon is already triangulated, and the score of the only triangle is 6.

Example 2

Input: values = [3,7,4,5]

Output: 144

There are two triangulations, with possible scores: 3 7 5 + 4 5 7 = 245, or 3 4 5 + 3 4 7 = 144. The minimum score is 144.

Example 3

Input: values = [1,3,1,4,1,5]

Output: 13

The minimum score triangulation is 1 1 3 + 1 1 4 + 1 1 5 + 1 1 1 = 13.

Constraints

n == values.length
3 <= n <= 50
1 <= values[i] <= 100

Solution Approach

Define subproblems using DP

Use a DP table dp[i][j] representing the minimum triangulation score for the subpolygon from vertex i to vertex j. The key state transition is choosing a vertex k between i and j to form a triangle with i and j, then recursively computing dp[i][k] + dp[k][j] + values[i]*values[j]*values[k].

Bottom-up computation

Iterate over increasing subpolygon lengths to fill the DP table. For each subpolygon of length >= 3, evaluate all possible k splits and update dp[i][j] with the minimal score. This approach avoids redundant recursion and leverages previously computed smaller subpolygons efficiently.

Return final minimal score

The answer is stored in dp[0][n-1], representing the minimal triangulation score for the full polygon. This ensures the DP correctly captures the optimal sum using the state transition pattern for all subproblems.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^3) because each of the O(n^2) subproblems checks O(n) possible k splits. Space complexity is O(n^2) for storing the DP table.

What Interviewers Usually Probe

Focus on state transition dynamic programming for polygon subproblems.
Check whether the DP correctly handles all subpolygon combinations.
Expect reasoning about triangle vertex products and minimal sums.

Common Pitfalls or Variants

Common pitfalls

Forgetting that a triangle must use original polygon vertices only.
Misindexing DP ranges or skipping subpolygons of length 3.
Not considering all possible k splits between i and j, missing minimal scores.

Follow-up variants

Compute maximal score instead of minimal by adjusting DP comparisons.
Allow polygons with negative vertex values affecting triangle weight.
Optimize for memory by using a rolling DP table if needed.

FAQ

What is the primary pattern for solving Minimum Score Triangulation of Polygon?

The key pattern is state transition dynamic programming, where dp[i][j] stores the minimal triangulation score for the subpolygon from vertex i to j.

Can the polygon vertices have negative values?

Yes, negative values are allowed, but the DP approach remains valid, summing triangle weights correctly.

Why do we need to consider every vertex k between i and j?

Each vertex k represents a possible triangle split. Considering all k ensures the DP captures the true minimal triangulation score.

What is the time complexity for this DP solution?

The solution runs in O(n^3) time due to checking all O(n) k splits for each of the O(n^2) subproblems.

How does the solution handle small polygons of length 3?

Subpolygons of length 3 form a single triangle, and dp[i][i+2] is directly assigned values[i]*values[i+1]*values[i+2].

terminal

Solution

Solution 1: Memoization

We design a function $\text{dfs}(i, j)$, which represents the minimum score after triangulating the polygon from vertex $i$ to $j$. The answer is $\text{dfs}(0, n - 1)$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i + 1 == j:
                return 0
            return min(
                dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]
                for k in range(i + 1, j)
            )

        return dfs(0, len(values) - 1)

Solution 2: Dynamic Programming

We can convert the memoization approach in Solution 1 into a dynamic programming approach.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i + 1 == j:
                return 0
            return min(
                dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]
                for k in range(i + 1, j)
            )

        return dfs(0, len(values) - 1)

Solution 3: Dynamic Programming (Alternative Implementation)

In Solution 2, we mentioned two enumeration strategies. Here, we use the second strategy: enumerate the interval length $l$ from small to large, where $3 \leq l \leq n$. Then, enumerate the left endpoint $i$ of the interval, and the right endpoint can be calculated as $j = i + l - 1$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i + 1 == j:
                return 0
            return min(
                dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]
                for k in range(i + 1, j)
            )

        return dfs(0, len(values) - 1)

Continue Practicing

#1035 uncrossed lines #1043 partition array for maximum sum #1031 maximum sum of two non overlapping subarrays