Minimum Score Triangulation of Polygon solution and explanation
Google
9 more videos on this problem
Minimum Score Triangulation of Polygon | Simplified for Beginners | Leetcode 1039 | codestorywithMIKcodestorywithMIK · 24:22 · 10K views
Minimum Score Triangulation of Polygon: Leetcode 1039Tony Teaches · 9:49 · 5K views
1039. Minimum Score Triangulation of Polygon | Leetcode Daily - PythonLeetcode Daily · 8:51 · 1K views
1039. Minimum Score Triangulation of Polygon (Leetcode Medium)Programming Live with Larry · 33:18 · 1K views
Daily Leetcode #2008: Sep 29, 2025 - 1039. Minimum Score Triangulation of PolygonProgramming Live with Larry · 29:26 · 792 views
Minimum Score Triangulation of Polygon | LeetCode 1039 - Pythonimpoldev · 11:03 · 492 views
Minimum Score Triangulation of Polygon | LeetCode 1039 | Dynamic Programming | Asked in GoogleCode Harmony · 21:35 · 476 views
1039. Minimum Score Triangulation of Polygon | Not Hard actually | Leetcode Daily ChallengeEye on AI and DSA · 22:19 · 402 views
LeetCode Daily 1039 | Minimum Score Triangulation of Polygon | MediumDaily Dose Of LeetCode · 19:11 · 353 views
leetCode 1039 in JavaScript - Minimum Score Triangulation of Polygon | JSer algorithm & JavaScriptJSer · 48:20 · 308 views
The problem
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] <= 100
Approach overview
Problem 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.
Approach 1: Dynamic Programming Approach
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.
def minScoreTriangulation(values):
n = len(values)
dp = [[0] * n for _ in range(n)]
for l in range(2, n):
for i in range(n - l):
j = i + l
dp[i][j] = float('inf')
for k in range(i + 1, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k])
return dp[0][n - 1]
values = [1, 3, 1, 4, 1, 5]
print(minScoreTriangulation(values))import java.util.Arrays;
public class MinScoreTriangulation {
public int minScoreTriangulation(int[] values) {
int n = values.length;
int[][] dp = new int[n][n];
for (int len = 2; len < n; len++) {
for (int i = 0; i + len < n; i++) {
int j = i + len;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i + 1; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
}
}
}
return dp[0][n - 1];
}
public static void main(String[] args) {
MinScoreTriangulation sol = new MinScoreTriangulation();
int[] values = {1, 3, 1, 4, 1, 5};
System.out.println(sol.minScoreTriangulation(values));
}
}#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int minScoreTriangulation(vector<int>& values) {
int n = values.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len < n; len++) {
for (int i = 0; i + len < n; i++) {
int j = i + len;
dp[i][j] = INT_MAX;
for (int k = i + 1; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
}
}
}
return dp[0][n - 1];
}
int main() {
vector<int> values = {1, 3, 1, 4, 1, 5};
cout << minScoreTriangulation(values) << endl;
return 0;
}function minScoreTriangulation(values) {
const n = values.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let len = 2; len < n; len++) {
for (let i = 0; i + len < n; i++) {
let j = i + len;
dp[i][j] = Infinity;
for (let k = i + 1; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
}
}
}
return dp[0][n - 1];
}
const values = [1, 3, 1, 4, 1, 5];
console.log(minScoreTriangulation(values));#include <stdio.h>
#include <limits.h>
int minScoreTriangulation(int* values, int valuesSize) {
int dp[50][50] = {0};
for (int len = 2; len < valuesSize; len++) {
for (int i = 0; i + len < valuesSize; i++) {
int j = i + len;
dp[i][j] = INT_MAX;
for (int k = i + 1; k < j; k++) {
dp[i][j] = fmin(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
}
}
}
return dp[0][valuesSize - 1];
}
int main() {
int vals[] = {1, 3, 1, 4, 1, 5};
int size = sizeof(vals) / sizeof(vals[0]);
printf("%d\n", minScoreTriangulation(vals, size));
return 0;
}using System;
public class Solution {
public int MinScoreTriangulation(int[] values) {
int n = values.Length;
int[,] dp = new int[n, n];
for (int len = 2; len < n; len++) {
for (int i = 0; i + len < n; i++) {
int j = i + len;
dp[i, j] = int.MaxValue;
for (int k = i + 1; k < j; k++) {
dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k, j] + values[i] * values[j] * values[k]);
}
}
}
return dp[0, n - 1];
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] values = {1, 3, 1, 4, 1, 5};
Console.WriteLine(solution.MinScoreTriangulation(values));
}
}This Python example illustrates a dynamic programming approach that constructs a dp matrix, where each entry dp[i][j] represents the minimum triangulation score possible from vertex i to vertex j. Two loops define the length of the sub-polygon, while the innermost loop calculates the minimum triangulation score.
Time Complexity: O(n^3), due to the three nested loops.
Space Complexity: O(n^2), for the dp matrix storage.
Approach 2: Memoization
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:
- If
i + 1 = j, it means the polygon has only two vertices and cannot be triangulated, so we return0; - Otherwise, we enumerate a vertex
kbetweeniandj, i.e.,i \lt k \lt j. Triangulating the polygon from vertexitojcan be divided into two subproblems: triangulating the polygon from vertexitokand triangulating the polygon from vertexktoj. The minimum scores of these two subproblems aredfs(i, k)anddfs(k, j), respectively. The score of the triangle formed by verticesi,j, andkisvalues[i] times values[k] times values[j]. Thus, the minimum score for this triangulation isdfs(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 ofdfs(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.
function minScoreTriangulation(values: number[]): number {
const n = values.length;
const f: number[][] = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));
const dfs = (i: number, j: number): number => {
if (i + 1 === j) {
return 0;
}
if (f[i][j] > 0) {
return f[i][j];
}
let ans = 1 << 30;
for (let k = i + 1; k < j; ++k) {
ans = Math.min(ans, dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]);
}
f[i][j] = ans;
return ans;
};
return dfs(0, n - 1);
}func minScoreTriangulation(values []int) int {
n := len(values)
f := [50][50]int{}
var dfs func(int, int) int
dfs = func(i, j int) int {
if i+1 == j {
return 0
}
if f[i][j] != 0 {
return f[i][j]
}
f[i][j] = 1 << 30
for k := i + 1; k < j; k++ {
f[i][j] = min(f[i][j], dfs(i, k)+dfs(k, j)+values[i]*values[k]*values[j])
}
return f[i][j]
}
return dfs(0, n-1)
}Approach 3: Dynamic Programming
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:
- Enumerate i
from large to small andjfrom small to large. This ensures that when calculating the statef[i][j], the statesf[i][k]andf[k][j]have already been computed. - Enumerate the interval length l
from small to large, where3 leq l leq n. Then enumerate the left endpointiof the interval, and the right endpoint can be calculated asj = i + l - 1. This also ensures that when calculating the larger intervalf[i][j], the smaller intervalsf[i][k]andf[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:
function minScoreTriangulation(values: number[]): number {
const n = values.length;
const f: number[][] = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));
for (let i = n - 3; i >= 0; --i) {
for (let j = i + 2; j < n; ++j) {
f[i][j] = 1 << 30;
for (let k = i + 1; k < j; ++k) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + values[i] * values[k] * values[j]);
}
}
}
return f[0][n - 1];
}func minScoreTriangulation(values []int) int {
n := len(values)
f := [50][50]int{}
for i := n - 3; i >= 0; i-- {
for j := i + 2; j < n; j++ {
f[i][j] = 1 << 30
for k := i + 1; k < j; k++ {
f[i][j] = min(f[i][j], f[i][k]+f[k][j]+values[i]*values[k]*values[j])
}
}
}
return f[0][n-1]
}Approach 4: 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.
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.
function minScoreTriangulation(values: number[]): number {
const n = values.length;
const f: number[][] = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));
for (let l = 3; l <= n; ++l) {
for (let i = 0; i + l - 1 < n; ++i) {
const j = i + l - 1;
f[i][j] = 1 << 30;
for (let k = i + 1; k < j; ++k) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + values[i] * values[k] * values[j]);
}
}
}
return f[0][n - 1];
}func minScoreTriangulation(values []int) int {
n := len(values)
f := [50][50]int{}
for l := 3; l <= n; l++ {
for i := 0; i+l-1 < n; i++ {
j := i + l - 1
f[i][j] = 1 << 30
for k := i + 1; k < j; k++ {
f[i][j] = min(f[i][j], f[i][k]+f[k][j]+values[i]*values[k]*values[j])
}
}
}
return f[0][n-1]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: Space Complexity: |
| Memoization | – |
| Dynamic Programming | – |
| Dynamic Programming (Alternative Implementation) | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Score Triangulation of Polygon easy or hard?
The problem is rated Medium on LeetCode. The difficulty comes from recognizing the interval dynamic programming pattern and defining the correct state dp[i][j]. Once the recurrence relation is clear, the implementation is straightforward.
Minimum Score Triangulation of Polygon Python/Java solution
Most implementations use the same interval DP logic across languages. Create a 2D dp array, iterate over increasing interval lengths, and try every possible middle vertex k to update the minimum cost. This works identically in Python, Java, C++, C#, JavaScript, and C.
How to solve Minimum Score Triangulation of Polygon in O(n^3)?
Use interval DP. Create a 2D table dp where dp[i][j] stores the minimum triangulation cost for vertices between i and j. For each interval length, iterate over all possible middle vertices k and update dp[i][j] with values[i] * values[k] * values[j] + dp[i][k] + dp[k][j]. This fills the table in O(n^3) time.
What is the best approach for Minimum Score Triangulation of Polygon?
The best approach is interval dynamic programming. Define dp[i][j] as the minimum score needed to triangulate the polygon between vertices i and j. For every possible middle vertex k between them, compute values[i] * values[k] * values[j] plus dp[i][k] and dp[k][j]. This approach runs in O(n^3) time with O(n^2) space.
Is Minimum Score Triangulation of Polygon asked at Google/Amazon/Meta?
Polygon triangulation and interval dynamic programming patterns appear in interviews at large tech companies including Google, Amazon, and Meta. The exact problem may vary, but the core idea of splitting ranges and minimizing cost using DP is commonly tested.
What data structure is used in Minimum Score Triangulation of Polygon?
The main structure is a 2D dynamic programming table (dp array). It stores the minimum triangulation cost for every vertex interval. The input itself is handled as an array of vertex values, while DP captures overlapping subproblems.
What is the time complexity of Minimum Score Triangulation of Polygon?
The optimal dynamic programming solution runs in O(n^3) time and O(n^2) space. There are O(n^2) subproblems defined by vertex pairs (i, j), and each state checks up to n possible split points k. Brute force recursion without memoization grows exponentially.