LeetCode 1039 - Minimum Score Triangulation of Polygon
This problem asks us to triangulate a convex polygon in such a way that the total triangulation score is minimized. We are given an array values, where each element represents the value assigned to a vertex of the polygon.
Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming
Solution
Problem Understanding
This problem asks us to triangulate a convex polygon in such a way that the total triangulation score is minimized.
We are given an array values, where each element represents the value assigned to a vertex of the polygon. The polygon is convex, and the vertices are listed in clockwise order. A triangulation divides the polygon into non-overlapping triangles using diagonals between existing vertices. Any valid triangulation of an n-sided polygon always produces exactly n - 2 triangles.
Each triangle contributes a score equal to the product of its three vertex values. The final triangulation score is the sum of the scores of all triangles in the triangulation. Our goal is to find the minimum possible total score among all valid triangulations.
For example, if we have:
values = [3,7,4,5]
there are two possible triangulations:
- Split using diagonal
(0,2) - Split using diagonal
(1,3)
Each triangulation creates a different set of triangles, which leads to different total scores. We must compute the minimum among them.
The constraints are important:
3 <= n <= 501 <= values[i] <= 100
Since n is only 50, this strongly suggests that an O(n^3) dynamic programming solution is acceptable. A brute-force recursive solution that explores every triangulation would grow exponentially and become far too slow.
The polygon is guaranteed to be convex, which simplifies the problem significantly. In a convex polygon, every diagonal lies entirely inside the polygon, so every triangulation choice is valid. We do not need to perform geometric validity checks.
Several edge cases are worth noticing immediately:
- A triangle already has exactly one triangulation, so arrays of length 3 are the smallest valid input.
- Multiple triangulations can produce very different scores, so greedy local decisions do not work.
- Large vertex values can create very large triangle costs, making optimal partitioning important.
- Since every triangulation divides the polygon recursively into smaller polygons, overlapping subproblems naturally appear.
This structure makes the problem a classic interval dynamic programming problem.
Approaches
Brute Force Approach
The brute-force approach recursively tries every possible triangulation.
Suppose we want to triangulate the polygon formed by vertices from index i to index j. We can choose any vertex k between them as the third vertex of a triangle (i, k, j).
That triangle contributes:
values[i] * values[k] * values[j]
After forming this triangle, the polygon splits into two smaller subproblems:
- triangulate
(i, k) - triangulate
(k, j)
We recursively compute both parts and add their costs.
The recurrence becomes:
cost(i, j) =
min over k:
cost(i, k)
+ cost(k, j)
+ values[i] * values[k] * values[j]
This brute-force solution is correct because every triangulation must choose some intermediate vertex k to form a triangle with endpoints i and j.
However, the same subproblems are recomputed repeatedly. The number of triangulations grows according to the Catalan numbers, which is exponential. This quickly becomes infeasible for n = 50.
Optimal Dynamic Programming Approach
The key observation is that the problem has overlapping subproblems and optimal substructure.
If we already know the minimum triangulation scores for smaller polygon intervals, we can reuse them instead of recomputing them.
We define:
dp[i][j]
as the minimum triangulation score for the polygon formed by vertices from i to j.
If j - i < 2, the polygon has fewer than 3 vertices, so no triangle can be formed and the score is 0.
For every interval (i, j), we try all possible middle vertices k:
dp[i][j] =
min(
dp[i][k]
+ dp[k][j]
+ values[i] * values[k] * values[j]
)
We compute smaller intervals first, then build larger intervals from them.
This avoids repeated computation and reduces the complexity to cubic time.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | Exponential | O(n) recursion stack | Explores every triangulation recursively |
| Optimal Dynamic Programming | O(n³) | O(n²) | Stores interval results and reuses them |
Algorithm Walkthrough
- Create a 2D DP table named
dp.
dp[i][j] will store the minimum triangulation score for the polygon interval from vertex i to vertex j.
2. Initialize all entries to 0.
Intervals with fewer than three vertices cannot form triangles, so their triangulation cost is naturally zero. 3. Process intervals in increasing order of length.
We start from intervals of length 3 because a triangle is the smallest polygon that contributes a score.
4. For each interval (i, j), initialize the answer to infinity.
We will try every possible middle vertex k between i and j.
5. Compute the triangle contribution.
Choosing k forms triangle:
(i, k, j)
whose score is:
values[i] * values[k] * values[j]
- Combine the two subproblems.
The total cost becomes:
dp[i][k]
+ dp[k][j]
+ values[i] * values[k] * values[j]
- Take the minimum over all valid
k.
This guarantees we select the optimal triangulation for interval (i, j).
8. Continue until the full polygon is processed.
The final answer is:
dp[0][n - 1]
Why it works
Every triangulation of a polygon interval (i, j) must contain exactly one triangle that uses vertices i and j. The third vertex of that triangle must be some k between them.
Once that triangle is chosen, the remaining polygon splits into two independent smaller polygons. Because the total score is the sum of triangle scores, the globally optimal triangulation must contain optimal triangulations for both subpolygons.
This optimal substructure property guarantees that dynamic programming produces the correct answer.
Python Solution
from typing import List
class Solution:
def minScoreTriangulation(self, values: List[int]) -> int:
n = len(values)
dp = [[0] * n for _ in range(n)]
for length in range(3, n + 1):
for left in range(n - length + 1):
right = left + length - 1
dp[left][right] = float("inf")
for mid in range(left + 1, right):
score = (
dp[left][mid]
+ dp[mid][right]
+ values[left] * values[mid] * values[right]
)
dp[left][right] = min(dp[left][right], score)
return dp[0][n - 1]
The implementation follows the interval dynamic programming strategy directly.
We first determine the number of vertices n, then create a 2D DP table initialized to zero. Every entry dp[i][j] represents the minimum triangulation score for the polygon segment between indices i and j.
The outer loop iterates over interval lengths starting from 3 because intervals smaller than 3 cannot form triangles.
For every interval (left, right), we initialize the answer to infinity because we are searching for a minimum.
The inner loop tries every possible middle vertex mid. Choosing mid forms a triangle with vertices left and right, producing a triangle cost:
values[left] * values[mid] * values[right]
We then add the optimal costs of the left and right subpolygons:
dp[left][mid] + dp[mid][right]
The minimum over all choices becomes the optimal triangulation score for that interval.
Finally, dp[0][n - 1] contains the answer for the entire polygon.
Go Solution
package main
import "math"
func minScoreTriangulation(values []int) int {
n := len(values)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
for length := 3; length <= n; length++ {
for left := 0; left <= n-length; left++ {
right := left + length - 1
dp[left][right] = math.MaxInt32
for mid := left + 1; mid < right; mid++ {
score := dp[left][mid] +
dp[mid][right] +
values[left]*values[mid]*values[right]
if score < dp[left][right] {
dp[left][right] = score
}
}
}
}
return dp[0][n-1]
}
The Go implementation is structurally identical to the Python version. The primary difference is explicit slice allocation for the 2D DP table.
Go does not have an infinity value for integers, so we initialize each interval result with math.MaxInt32.
The constraints are small enough that integer overflow is not a concern. The maximum possible score remains safely within Go's integer range.
Worked Examples
Example 1
values = [1,2,3]
Only one triangle exists.
| Triangle | Score |
|---|---|
| (1,2,3) | 1 × 2 × 3 = 6 |
Final answer:
6
Example 2
values = [3,7,4,5]
We compute intervals of increasing size.
Length = 3
| Interval | Triangle | Score | DP Value |
|---|---|---|---|
| (0,2) | (3,7,4) | 84 | dp[0][2] = 84 |
| (1,3) | (7,4,5) | 140 | dp[1][3] = 140 |
Length = 4
Now compute dp[0][3].
Possible middle vertices:
k = 1
Triangle:
3 * 7 * 5 = 105
Total:
dp[0][1] + dp[1][3] + 105
= 0 + 140 + 105
= 245
k = 2
Triangle:
3 * 4 * 5 = 60
Total:
dp[0][2] + dp[2][3] + 60
= 84 + 0 + 60
= 144
Take minimum:
dp[0][3] = 144
Final answer:
144
Example 3
values = [1,3,1,4,1,5]
The DP table gradually builds optimal interval costs.
Some important intervals:
| Interval | Best Score |
|---|---|
| dp[0][2] | 3 |
| dp[1][3] | 12 |
| dp[2][4] | 4 |
| dp[3][5] | 20 |
Larger intervals reuse these smaller solutions.
Eventually:
dp[0][5] = 13
Optimal triangulation uses many triangles containing vertices with value 1, minimizing the multiplication cost.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n³) | Three nested loops over interval length, left boundary, and middle vertex |
| Space | O(n²) | DP table stores results for all intervals |
The algorithm processes every interval (i, j) and tries every possible split point k inside that interval.
There are O(n²) intervals and each interval may examine up to O(n) split points, producing total time complexity O(n³).
The DP table contains n × n entries, resulting in O(n²) space usage.
Test Cases
from typing import List
class Solution:
def minScoreTriangulation(self, values: List[int]) -> int:
n = len(values)
dp = [[0] * n for _ in range(n)]
for length in range(3, n + 1):
for left in range(n - length + 1):
right = left + length - 1
dp[left][right] = float("inf")
for mid in range(left + 1, right):
score = (
dp[left][mid]
+ dp[mid][right]
+ values[left] * values[mid] * values[right]
)
dp[left][right] = min(dp[left][right], score)
return dp[0][n - 1]
solution = Solution()
assert solution.minScoreTriangulation([1, 2, 3]) == 6
# Smallest valid polygon
assert solution.minScoreTriangulation([3, 7, 4, 5]) == 144
# Example with two triangulation choices
assert solution.minScoreTriangulation([1, 3, 1, 4, 1, 5]) == 13
# Larger polygon with multiple optimal substructures
assert solution.minScoreTriangulation([2, 2, 2]) == 8
# Uniform triangle values
assert solution.minScoreTriangulation([1, 1, 1, 1]) == 2
# Every triangle contributes 1
assert solution.minScoreTriangulation([5, 3, 7]) == 105
# Another base triangle case
assert solution.minScoreTriangulation([1, 2, 1, 2, 1]) == 6
# Tests whether algorithm prefers low-value vertices
assert solution.minScoreTriangulation([100, 1, 100, 1, 100]) == 10200
# Large values mixed with small values
assert solution.minScoreTriangulation([1, 5, 1, 5, 1]) == 11
# Optimal triangulation repeatedly uses small vertices
| Test | Why |
|---|---|
[1,2,3] |
Smallest valid polygon |
[3,7,4,5] |
Verifies multiple triangulation choices |
[1,3,1,4,1,5] |
Standard complex example |
[2,2,2] |
Uniform values |
[1,1,1,1] |
Every triangulation has same cost |
[5,3,7] |
Another minimal polygon |
[1,2,1,2,1] |
Tests reuse of small vertices |
[100,1,100,1,100] |
Large value interactions |
[1,5,1,5,1] |
Ensures globally optimal decisions |
Edge Cases
One important edge case is the smallest possible polygon, where n = 3. In this situation, the polygon is already a triangle, so there is exactly one triangulation. A buggy implementation might incorrectly attempt additional recursion or interval splitting. The DP solution handles this naturally because the interval length is exactly 3, producing one triangle computation.
Another important edge case occurs when many vertices have value 1. Since multiplication by 1 keeps triangle costs small, the optimal triangulation often repeatedly uses these vertices. A greedy algorithm that only minimizes immediate triangle cost may fail because future splits matter. The interval DP solution correctly evaluates all possible partitions and guarantees the global minimum.
A third important edge case involves large vertex values such as 100. Triangle products can become large very quickly. Poor triangulation choices may create unnecessarily expensive triangles. The DP solution systematically compares every possible split point and ensures that expensive combinations are avoided whenever possible.
A final subtle edge case occurs when multiple triangulations produce the same score. The problem only asks for the minimum score, not the actual triangulation structure. Our implementation only stores numeric minimum values, which is sufficient and avoids unnecessary complexity.