You have a convex n-sided polygon where each vertex has an integer value. You are given an integer array values where values[i] is the value of the ith vertex in clockwise order.
Polygon triangulation is a process where you divide a polygon into a set of triangles and the vertices of each triangle must also be vertices of the original polygon. Note that no other shapes other than triangles are allowed in the division. This process will result in n - 2 triangles.
You will triangulate the polygon. For each triangle, the weight of that triangle is the product of the values at its vertices. The total score of the triangulation is the sum of these weights over all n - 2 triangles.
Return the minimum possible score that you can achieve with some triangulation of the polygon.
Example 1:
Input: values = [1,2,3]
Output: 6
Explanation: The polygon is already triangulated, and the score of the only triangle is 6.
Example 2:
Input: values = [3,7,4,5]
Output: 144
Explanation: 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
Explanation: The minimum score triangulation is 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.
Constraints:
n == values.length3 <= n <= 501 <= values[i] <= 100Problem Overview: You are given a convex polygon where each vertex has a value. When you triangulate the polygon, each triangle contributes a score equal to the product of its three vertex values. The task is to split the polygon into triangles so the total score is minimized.
Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)
The polygon triangulation problem can be expressed recursively. Pick two boundary vertices i and j. Any vertex k between them can form a triangle (i, k, j). The total score becomes values[i] * values[k] * values[j] plus the cost of triangulating the left subpolygon (i, k) and the right subpolygon (k, j). Trying every possible k explores all triangulations, which leads to exponential time because the same subproblems repeat many times.
Approach 2: Top-Down Dynamic Programming with Memoization (O(n^3) time, O(n^2) space)
The key observation: subpolygons appear repeatedly during recursion. Store results for each pair of vertices (i, j). When computing the minimum triangulation score between them, iterate k from i+1 to j-1, compute the triangle score, and combine it with the cached results of the left and right segments. Memoization avoids recomputation and reduces the complexity to O(n^3) because there are O(n^2) states and each state tries up to n splits. This technique is a classic example of dynamic programming applied to polygon partitioning.
Approach 3: Bottom-Up Interval DP (O(n^3) time, O(n^2) space)
The iterative version builds solutions for smaller polygon intervals first. Define dp[i][j] as the minimum score needed to triangulate vertices from index i to j. Start with small gaps and expand outward. For every pair (i, j) where at least one triangle can be formed (j - i >= 2), iterate k between them and compute values[i] * values[k] * values[j] + dp[i][k] + dp[k][j]. Update dp[i][j] with the minimum value. This interval-based DP ensures that when computing dp[i][j], the required subproblems are already solved. The input is handled as an array, while the transition logic mirrors classic interval partition problems.
Recommended for interviews: The bottom-up dynamic programming approach is the expected solution. Interviewers want to see whether you recognize the interval DP pattern and correctly define the state dp[i][j]. Starting with the recursive idea shows you understand the triangulation structure, while converting it to O(n^3) DP demonstrates strong algorithmic reasoning.
This problem is a classic example of Dynamic Programming. The idea is to partition the polygon using dynamic programming where you maintain a dp table, dp[i][j] represents the minimum score to triangulate a polygon starting from vertex i to vertex j.
To solve the problem, we iterate through all possible partitions and calculate their respective scores, updating the dp table to reflect the minimum scores possible for triangulating various sub-polygons.
This C code uses a dynamic programming approach to solve the polygon triangulation problem. The dp table, dp[i][j], stores the minimum score for triangulating the sub-polygon from vertex i to vertex j. We iterate over possible lengths len of the sub-polygons, then calculate the minimum score considering the product of the chosen vertices.
Time Complexity: O(n^3), where n is the number of vertices in the polygon, due to the three nested loops.
Space Complexity: O(n^2), for storing the dp table.
We design a function dfs(i, j), which represents the minimum score after triangulating the polygon from vertex i to j. The answer is dfs(0, n - 1).
The calculation process of dfs(i, j) is as follows:
i + 1 = j, it means the polygon has only two vertices and cannot be triangulated, so we return 0;k between i and j, i.e., i \lt k \lt j. Triangulating the polygon from vertex i to j can be divided into two subproblems: triangulating the polygon from vertex i to k and triangulating the polygon from vertex k to j. The minimum scores of these two subproblems are dfs(i, k) and dfs(k, j), respectively. The score of the triangle formed by vertices i, j, and k is values[i] times values[k] times values[j]. Thus, the minimum score for this triangulation is dfs(i, k) + dfs(k, j) + values[i] times values[k] times values[j]. We take the minimum value of all possibilities, which is the value of dfs(i, j).To avoid repeated calculations, we can use memoization, i.e., use a hash table or an array to store the already computed function values.
Finally, we return dfs(0, n - 1).
The time complexity is O(n^3), and the space complexity is O(n^2), where n is the number of vertices in the polygon.
Python
Java
C++
Go
TypeScript
We can convert the memoization approach in Solution 1 into a dynamic programming approach.
Define f[i][j] as the minimum score after triangulating the polygon from vertex i to j. Initially, f[i][j] = 0, and the answer is f[0][n-1].
For f[i][j] (where i + 1 \lt j), we first initialize f[i][j] to infty.
We enumerate a vertex k between i and j, i.e., i \lt k \lt j. Triangulating the polygon from vertex i to j can be divided into two subproblems: triangulating the polygon from vertex i to k and triangulating the polygon from vertex k to j. The minimum scores of these two subproblems are f[i][k] and f[k][j], respectively. The score of the triangle formed by vertices i, j, and k is values[i] times values[k] times values[j]. Thus, the minimum score for this triangulation is f[i][k] + f[k][j] + values[i] times values[k] times values[j]. We take the minimum value of all possibilities, which becomes the value of f[i][j].
In summary, we can derive the state transition equation:
$
f[i][j]=
\begin{cases}
0, & i+1=j \
infty, & i+1<j \
min_{i<k<j} {f[i][k]+f[k][j]+values[i] times values[k] times values[j]}, & i+1<j
\end{cases}
Note that when enumerating i and j, there are two possible enumeration strategies:
from large to small and j from small to large. This ensures that when calculating the state f[i][j], the states f[i][k] and f[k][j] have already been computed. 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. This also ensures that when calculating the larger interval f[i][j], the smaller intervals f[i][k] and f[k][j] have already been computed.Finally, we return f[0][n-1].
The time complexity is O(n^3), and the space complexity is O(n^2), where n$ is the number of vertices in the polygon.
Related problems:
Python
Java
C++
Go
TypeScript
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.
The time complexity is O(n^3), and the space complexity is O(n^2), where n is the number of vertices in the polygon.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: Space Complexity: |
| Memoization | — |
| Dynamic Programming | — |
| Dynamic Programming (Alternative Implementation) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(2^n) | O(n) | Useful for understanding the recursive structure of polygon triangulation |
| Top-Down DP (Memoization) | O(n^3) | O(n^2) | When converting recursion to a cached solution with overlapping subproblems |
| Bottom-Up Interval DP | O(n^3) | O(n^2) | Best general solution for interviews and production implementations |
Minimum Score Triangulation of Polygon | Simplified for Beginners | Leetcode 1039 | codestorywithMIK • codestorywithMIK • 10,292 views views
Watch 9 more video solutions →Practice Minimum Score Triangulation of Polygon with our built-in code editor and test cases.
Practice on FleetCode