Minimum Score Triangulation of Polygon — Problem & Solution
Minimum Score Triangulation of Polygon solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Score Triangulation of Polygon is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A convex polygon has n vertices, and values[i] is the label of the i-th vertex in clockwise order.
Cut the polygon into n - 2 triangles using non-crossing diagonals (a triangulation). Each triangle scores the product of the labels of its three vertices, and a triangulation scores the sum of its triangles' scores.
Return the smallest score any triangulation can achieve.
Example 1
Input: values = [2,4,3]
Output: 24
Explanation: Already a triangle: 2 · 4 · 3.
Example 2
Input: values = [1,5,2,4]
Output: 18
Explanation: Diagonal 0–2 gives 1·5·2 + 1·2·4 = 18; diagonal 1–3 gives 60.
Example 3
Input: values = [1,3,1,4,1,5]
Output: 13
Constraints
n == values.length3 <= n <= 501 <= values[i] <= 100
Hints for Minimum Score Triangulation of Polygon
Hint 1
In any triangulation, the edge between vertex 0 and vertex n-1 belongs to exactly one triangle.
Hint 2
If that triangle's third vertex is
k, the rest splits into two independent smaller polygons:0..kandk..n-1.Hint 3
Let
dp[i][j]be the best score for the polygon formed by verticesi..j; try everykstrictly between them.
How to solve Minimum Score Triangulation of Polygon
Interval DP. For the sub-polygon on vertices i..j, the side (i, j) lies in exactly one triangle (i, k, j), and choosing k splits the remainder into the sub-polygons i..k and k..j.
Approach
dp[i][j] = 0whenj - i < 2(an edge, nothing to triangulate).- For increasing gap
j - ifrom 2 ton - 1:dp[i][j] = min over i < k < j of dp[i][k] + dp[k][j] + values[i]·values[k]·values[j]. - Return
dp[0][n-1].
Why it works
Every triangulation of i..j contains exactly one triangle on the side (i, j), and the diagonals (i, k) and (k, j) separate the rest into two polygons that are triangulated independently. Taking the minimum over all k therefore covers every triangulation, and the two halves can each be chosen optimally on their own.
Complexity
- Time —
O(n³) - Space —
O(n²)
Pitfalls
- Fill the table by increasing interval length so both halves are ready.
- The polygon is cyclic, but fixing the side
(0, n-1)removes the need for wrap-around. - The answer can reach about 5·10^7, which fits in 32 bits — no modulus is involved.
Reference solution
Python
from typing import List
def minScoreTriangulation(values: List[int]) -> int:
n = len(values)
dp = [[0] * n for _ in range(n)]
for gap in range(2, n):
for i in range(n - gap):
j = i + gap
best = -1
for k in range(i + 1, j):
cand = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]
if best < 0 or cand < best:
best = cand
dp[i][j] = best
return dp[0][n - 1]Java
public static int minScoreTriangulation(int[] values) {
int n = values.length;
int[][] dp = new int[n][n];
for (int gap = 2; gap < n; gap++) {
for (int i = 0; i + gap < n; i++) {
int j = i + gap;
int best = -1;
for (int k = i + 1; k < j; k++) {
int cand = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
if (best < 0 || cand < best) best = cand;
}
dp[i][j] = best;
}
}
return dp[0][n - 1];
}C++
int minScoreTriangulation(vector<int>& values) {
int n = values.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int gap = 2; gap < n; gap++) {
for (int i = 0; i + gap < n; i++) {
int j = i + gap;
int best = -1;
for (int k = i + 1; k < j; k++) {
int cand = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
if (best < 0 || cand < best) best = cand;
}
dp[i][j] = best;
}
}
return dp[0][n - 1];
}JavaScript
var minScoreTriangulation = function(values) {
var n = values.length;
var dp = [];
for (var i = 0; i < n; i++) dp.push(new Array(n).fill(0));
for (var gap = 2; gap < n; gap++) {
for (i = 0; i + gap < n; i++) {
var j = i + gap;
var best = -1;
for (var k = i + 1; k < j; k++) {
var cand = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
if (best < 0 || cand < best) best = cand;
}
dp[i][j] = best;
}
}
return dp[0][n - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming