Cutting a Polygon Into Triangles
A convex polygon has n vertices, labelled 0 to n-1 in order around the boundary,
each holding a value. Cut it into triangles using non-crossing diagonals. A triangle scores
the PRODUCT of its three vertex values, and the total score is the sum over all triangles.
Print the smallest achievable total.
1 2 3 -> 6 already a triangle, 1 * 2 * 3
3 7 4 5 -> 144
1 1 1 1 -> 2 two triangles, each scoring 1
## The edge that forces the structure
Take any EDGE of the polygon, say the one joining vertex i to vertex j. In any
triangulation that edge belongs to exactly one triangle, whose third vertex is some k
between them.
That triangle splits the rest of the polygon into two smaller polygons: the one on the
i..k side and the one on the k..j side. They share no interior, so they are independent.
That is the interval split, and it comes from a geometric fact rather than from an ordering. Worth noticing: the "interval" here is an arc of the boundary, not a range of an array, and the DP does not care about the difference.
## The recurrence
dp[i][j] = the smallest score for the polygon on vertices i, i+1, ..., j
dp[i][j] = 0 when j - i < 2 fewer than three vertices, no triangle
dp[i][j] = min over k in (i, j) of dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]
The answer is dp[0][n-1].
## Why the base case is j - i < 2
An interval spanning fewer than three vertices is a single edge or a single point, which contains no triangle and scores 0.
Setting it to anything else adds phantom triangles. Setting the base at j - i < 1 instead
lets a two-vertex "polygon" be triangulated, which reads out of range.
## Why the chord is the whole polygon edge only at the top
dp[0][n-1] treats the chord from vertex 0 to vertex n-1 as an edge, which it is: those
two vertices are adjacent around the boundary. Inside the recursion the chord (i, j) is a
DIAGONAL rather than an edge, and the recurrence does not distinguish them, which is exactly
why one formula covers both.
## Boundaries
A triangle answers the product of its three vertices, which is why 1 2 3 answers 6 and
5 5 5 answers 125.
1 1 1 1 answers 2: a square splits into two triangles whatever diagonal is chosen, and
each scores 1.
1 5 1 5 answers 10: the two diagonals give 1*5*1 + 1*1*5 = 10 and 5*1*5 + 5*5*1 = 50,
so the choice matters even at four vertices.
## Cost
Time O(n^3). Space O(n^2).
## Where this appears again
Splitting on the triangle containing a fixed edge is the standard treatment of polygon triangulation, and the same counting gives the Catalan numbers when the objective is "how many triangulations". It is structurally identical to matrix chain multiplication, which is not a coincidence: a bracketing of a product is a triangulation of a polygon.