← DSA Atlas
Dedicated problem page · #1039

Minimum Score Triangulation of Polygon

MediumTwo-Dimensional Dynamic ProgrammingInterval DP splitting on a triangle apexInterval dynamic programming
Solve on LeetCode ↗
1039
MediumTwo-Dimensional Dynamic ProgrammingInterval dynamic programmingInterval DP splitting on a triangle apex

Minimum Score Triangulation of Polygon

Given a convex polygon with n vertices labeled by the array values in clockwise order, triangulate it into n-2 triangles. Each triangle's score is the product of its three vertex labels, and the triangulation's total score is the sum of those products. Return the minimum possible total score over all triangulations.

Open official problem prompt ↗
In plain English

Find the cheapest way to cut a convex polygon into triangles when each triangle costs the product of its corner labels.

Picture it like this

Like framing a stained-glass panel from a wide pane: you pick one diagonal beam at a time, which necessarily leaves two smaller panes you frame independently, and you want the cheapest set of beams overall.

Example
Input
values = [3, 7, 4, 5]
Output
144
Why
Triangulating with the diagonal 3-4 gives triangles (3,7,4)=84 and (3,4,5)=60, totaling 144, the minimum.
Constraints
n == values.length3 <= n <= 501 <= values[i] <= 100
Pattern lesson

See the pattern, then code

Interval DP splitting on a triangle apex
Recognition clue

You must optimally split a polygon into triangles, and each split creates two independent sub-polygons sharing an edge; that decomposition over vertex ranges is interval DP.

↗
Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. Fix the edge from vertex i to vertex j as the base. Some third vertex k between them forms a triangle with that base, splitting the polygon into sub-polygon (i..k) and sub-polygon (k..j). Sum the triangle's product with both sub-solutions and minimize over k.

New words, made simpleKnow these before the algorithm
Triangulation
A decomposition of a polygon into non-overlapping triangles using its vertices.
Apex
The third vertex k chosen to form a triangle with the fixed base edge (i, j).
Sub-polygon
The smaller polygon left on either side of the chosen triangle, solved recursively.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Enumerate all triangulations

The number of triangulations grows like Catalan numbers; infeasible.

Generate every possible triangulation and sum each.

Time Catalan(n) exponentialSpace O(n)
Split on a diagonal, memoized

Correct; the bottom-up table is the same idea without recursion overhead.

Recurse on ranges, caching results.

Time O(n^3)Space O(n^2)
Best choiceBottom-up interval DP

Standard and efficient for n up to 50.

dp[i][j] minimized over the apex k for the base edge (i, j).

Time O(n^3)Space O(n^2)
The rule we keep true

Invariant

dp[i][j] is the minimum total triangulation score of the polygon formed by vertices i, i+1, ..., j with the edge (i, j) as one of its sides.

Why this is correct

Reasoning

In any triangulation, the base edge (i, j) belongs to exactly one triangle, whose apex is some vertex k between i and j. That triangle partitions the polygon into the sub-polygon on vertices i..k and the one on k..j, which are triangulated independently. Trying every k covers all triangulations containing edge (i, j), so the minimum is optimal.

The algorithm in three movesSay these aloud before coding
1Let dp[i][j] be the minimum triangulation score of the polygon spanning vertices i through j

dp[i][i+1] = 0 (an edge, no triangle)

2Base case: any range shorter than 3 vertices has zero score

dp[0][2] = 3*7*4 = 84

3For each range, try every apex k strictly between i and j

dp[0][3] = min(dp[0][2]+3*4*5, ...) = 84 + 60 = 144

4dp[i][j] = min over k of dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]

5Grow ranges by increasing length; return dp[0][n-1]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
71
42
53
1 · Readvalues = [3,7,4,5]
2 · AskRanges of length 1 (adjacent vertices)?
3 · Update statedp[i][i+1] = 0
4 · ResultNo triangle on a bare edge
Key takeaway

The base edge from vertex 0 to vertex 3 with apex k splitting the polygon into two parts.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Table init

    Zero-initialized dp doubles as the base case: ranges of fewer than three vertices cost 0.

  2. 2
    Lines 5-7Grow ranges

    Length starts at 2 so j = i + length spans at least three vertices, the smallest triangle.

  3. 3
    Lines 8-12Minimize over apex

    Each k forms a triangle with base (i, j); add its product to both sub-polygon costs and keep the minimum.

  4. 4
    Lines 13Answer

    dp[0][n-1] covers the whole polygon.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Exactly 3 vertices: single triangle, answer is the product of all three
  • All values equal: still O(n^3) evaluation, minimum picks balanced splits
  • Small values keep products low but the structure is unchanged
!

Common beginner mistakes

  • Indexing the loop so ranges of length 1 are treated as triangles (they must cost 0)
  • Using dp[i][k-1] or dp[k+1][j] instead of dp[i][k] and dp[k][j]; the shared apex k is a boundary of both sub-polygons
  • Trying to be greedy about the cheapest triangle first, which is not optimal
Check your understanding

Why fix the edge (i, j) and vary the apex k instead of fixing a vertex?

More in Two-Dimensional Dynamic Programming

#1143Longest Common SubsequenceSequence-alignment grid DP#72Edit DistanceSequence-alignment grid DP#10Regular Expression MatchingPattern-matching grid DP with star lookback#44Wildcard MatchingGlob-matching grid DP#62Unique PathsGrid path-counting DP#63Unique Paths IIGrid path-counting DP with obstacles