Minimum Score Triangulation of Polygon
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the recursive structure of the problem into a function. The problem of triangulating a polygon with vertices i to j can be broken down by choosing a third vertex k (where i < k < j) to form a triangle (i, k, j). This triangle splits the problem into two smaller subproblems: triangulating the polygon from i to k and triangulating the polygon from k to j. The total score for this choice of k is the sum of the scores of the two subproblems plus the score of the triangle (i, k, j). We try all possible k and take the minimum.
Algorithm
- Define a recursive function
solve(values, i, j)that computes the minimum triangulation score for the polygon formed by verticesvalues[i], ..., values[j]. - The base case for the recursion is when there are fewer than 3 vertices (i.e.,
j < i + 2). In this scenario, no triangles can be formed, so the function returns 0. - Initialize a variable
minScoreto a very large value (e.g.,Integer.MAX_VALUE). - Iterate through all possible intermediate vertices
kfromi + 1toj - 1. Eachkforms a triangle(i, k, j). - For each
k, the total score is the sum of the score of the triangle(i, k, j)and the scores of the resulting sub-polygons. This is calculated recursively assolve(i, k) + solve(k, j) + values[i] * values[k] * values[j]. - Update
minScorewith the minimum value found across all choices ofk. - Return
minScore. - The main function calls
solve(values, 0, n-1)to get the final answer, wherenis the number of vertices.
Walkthrough
The core idea is to define a recursive function, say solve(i, j), which calculates the minimum triangulation score for the polygon formed by vertices values[i], values[i+1], ..., values[j]. The recurrence relation is:
solve(i, j) = min_{i < k < j} (solve(i, k) + solve(k, j) + values[i] * values[k] * values[j])
The base case for the recursion is when the sub-polygon has fewer than 3 vertices (i.e., j < i + 2). In this case, no triangles can be formed, so the score is 0. The final answer is obtained by calling solve(0, n-1).
class Solution { public int minScoreTriangulation(int[] values) { return solve(values, 0, values.length - 1); } private int solve(int[] values, int i, int j) { // Base case: if there are less than 3 vertices, no triangle can be formed. if (j < i + 2) { return 0; } int minScore = Integer.MAX_VALUE; // k is the middle vertex of the triangle (i, k, j) for (int k = i + 1; k < j; k++) { int currentScore = solve(values, i, k) + solve(values, k, j) + values[i] * values[k] * values[j]; minScore = Math.min(minScore, currentScore); } return minScore; }}Complexity
Time
Exponential, roughly O(2^n). The number of subproblems grows exponentially, leading to a very slow solution.
Space
O(n), for the recursion stack depth.
Trade-offs
Pros
Simple to understand and implement as it directly follows the problem's recursive definition.
Cons
Extremely inefficient due to a massive number of re-computations for the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
This approach improves upon the plain recursion by caching the results of subproblems to avoid re-computation. We use a 2D array, say memo, to store the computed minimum scores for sub-polygons. memo[i][j] will store the result of solve(i, j). Before computing the result for a subproblem (i, j), we first check if memo[i][j] has already been computed. If it has, we return the stored value. Otherwise, we compute it, store it in memo[i][j], and then return it.
Algorithm
- Initialize an
n x nmemoization tablememowith a sentinel value (e.g., 0, since scores are positive). - Define a recursive function
solve(i, j). - Base case: if
j < i + 2, return 0. - Memoization check: if
memo[i][j]is not the sentinel value, it means the result for this subproblem has been computed, so returnmemo[i][j]. - If the result is not memoized, initialize
minScoreto a large value. - Iterate
kfromi + 1toj - 1. - For each
k, recursively callsolveto get the score:solve(i, k) + solve(k, j) + values[i] * values[k] * values[j]. - Update
minScorewith the minimum score found. - Store the computed
minScoreinmemo[i][j]before returning it. - The initial call is
solve(0, n-1).
Walkthrough
This is a standard optimization for recursive solutions with overlapping subproblems, also known as top-down dynamic programming. We introduce a 2D array memo[n][n] initialized with a value indicating that the state has not been computed (e.g., 0, since scores are guaranteed to be positive).
The recursive function solve(i, j) is modified as follows:
- At the beginning of the function, check if
memo[i][j]is already computed. If so, returnmemo[i][j]. - If not, proceed with the calculation as in the recursive approach.
- Before returning the calculated
minScore, store it inmemo[i][j].
class Solution { private int[][] memo; private int[] values; public int minScoreTriangulation(int[] values) { this.values = values; int n = values.length; this.memo = new int[n][n]; return solve(0, n - 1); } private int solve(int i, int j) { // Base case: if there are less than 3 vertices, no triangle can be formed. if (j < i + 2) { return 0; } // Check if the result is already memoized. if (memo[i][j] != 0) { return memo[i][j]; } int minScore = Integer.MAX_VALUE; // k is the middle vertex of the triangle (i, k, j) for (int k = i + 1; k < j; k++) { int currentScore = solve(i, k) + solve(k, j) + values[i] * values[k] * values[j]; minScore = Math.min(minScore, currentScore); } // Memoize the result before returning. memo[i][j] = minScore; return minScore; }}Complexity
Time
O(n^3). There are O(n^2) unique subproblems `(i, j)`. Each subproblem takes O(n) time to compute (due to the loop over `k`). Since each subproblem is solved only once, the total time is O(n^2 * n) = O(n^3).
Space
O(n^2) for the memoization table, plus O(n) for the recursion stack depth. The total space is dominated by the table, so it's O(n^2).
Trade-offs
Pros
Much more efficient than plain recursion, avoiding redundant calculations.
Guaranteed to pass within the time limits for
n <= 50.Often more intuitive to write than the bottom-up approach if one thinks recursively.
Cons
Can lead to a
StackOverflowErrorfor very largen(though not an issue forn <= 50).Has the overhead of recursive function calls, which can be slightly slower than an iterative approach.
This is an iterative approach that systematically solves all subproblems, starting from the smallest ones and building up to the final solution. This is also known as bottom-up dynamic programming. We use a 2D DP table, dp[n][n], where dp[i][j] stores the minimum triangulation score for the polygon with vertices from i to j. We fill this table by iterating over the length of the sub-polygon, ensuring that when we compute dp[i][j], the values for smaller subproblems (dp[i][k] and dp[k][j]) are already available.
Algorithm
- Create an
n x nDP table,dp, and initialize it with 0s. - Iterate over the
gapfrom 2 ton-1. Thegaprepresents the length of the polygon chain (j - i). - For each
gap, iterate over the starting indexifrom 0 up ton - 1 - gap. - Calculate the ending index
j = i + gap. - Initialize
dp[i][j]to a very large value. - Iterate through all possible splitting vertices
kfromi + 1toj - 1. - For each
k, calculate the score for the current split using previously computed values:dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]. - Update
dp[i][j]with the minimum score found among allk. - After the loops complete,
dp[0][n-1]will hold the minimum score for the entire polygon. Return this value.
Walkthrough
We iterate over the 'gap' or length of the sub-polygon, from 2 up to n-1. The gap g represents j - i.
- The outer loop iterates
gfrom 2 ton-1. - The inner loop iterates through the starting vertex
ifrom 0 ton-1-g. The ending vertexjisi + g. - For each pair
(i, j), we calculatedp[i][j]using the same recurrence relation as before:dp[i][j] = min_{i < k < j} (dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]) - The base cases
dp[i][i+1](gap=1) are implicitly 0, as ourdptable is initialized to zeros and the loops forgstart from 2. - The final answer is stored in
dp[0][n-1].
class Solution { public int minScoreTriangulation(int[] values) { int n = values.length; int[][] dp = new int[n][n]; // gap is the length of the sub-polygon chain (j - i) for (int gap = 2; gap < n; gap++) { for (int i = 0; i < n - gap; i++) { int j = i + gap; dp[i][j] = Integer.MAX_VALUE; // k is the splitting vertex for (int k = i + 1; k < j; k++) { int score = dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]; dp[i][j] = Math.min(dp[i][j], score); } } } return dp[0][n - 1]; }}Complexity
Time
O(n^3). There are three nested loops. The outer loop for `gap` runs O(n) times. The middle loop for `i` runs O(n) times. The inner loop for `k` also runs O(n) times. This gives a total time complexity of O(n^3).
Space
O(n^2), for the 2D DP table.
Trade-offs
Pros
Avoids recursion overhead and the risk of stack overflow, making it very robust.
Generally the most performant solution in practice due to better memory access patterns and no function call overhead.
It's the most efficient standard approach for this problem.
Cons
Can be slightly less intuitive to formulate and implement compared to the top-down recursive approach.
Solutions
Solution
class Solution {private int n;private int[] values;private Integer[][] f;public int minScoreTriangulation(int[] values) { n = values.length; this.values = values; f = new Integer[n][n]; return dfs(0, n - 1); }private int dfs(int i, int j) { if (i + 1 == j) { return 0; } if (f[i][j] != null) { return f[i][j]; } int ans = 1 << 30; for (int k = i + 1; k < j; ++k) { ans = Math.min(ans, dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]); } return f[i][j] = ans; }}class Solution {public: int minScoreTriangulation(vector<int> &values) { int n = values.size(); int f[n][n]; memset(f, 0, sizeof(f)); function<int(int, int)> dfs = [&](int i, int j) -> int { if (i + 1 == j) { return 0; } if (f[i][j]) { return f[i][j]; } int ans = 1 << 30; for (int k = i + 1; k < j; ++k) { ans = min(ans, dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]); } return f[i][j] = ans; }; return dfs(0, n - 1); }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.