Lightest Polygon Triangulation
Medium2-D Dynamic Programming
Problem
A convex polygon has its vertices labelled in clockwise order with positive weights weights. Triangulating it means drawing non-crossing diagonals until it is divided into n - 2 triangles.
The weight of a triangle is the product of the weights of its three corners, and the weight of a triangulation is the sum over its triangles. Return the minimum possible weight.
Example 1
- Input:
- weights = [1, 4, 2, 3]
- Output:
- 14
The diagonal 0–2 gives triangles (1·4·2) + (1·2·3) = 8 + 6 = 14; the other diagonal gives 12 + 24 = 36.
Example 2
- Input:
- weights = [2, 2, 2]
- Output:
- 8
A triangle is already triangulated.
Constraints
- 3 ≤ weights.length ≤ 50
- 1 ≤ weights[i] ≤ 100
Hint
Show the first hint
The edge between the first and last vertex belongs to exactly one triangle. What is its third corner?
Walkthrough
How to approach it
01Clarify before coding
- Is the polygon convex? Yes, so every diagonal is valid and only the combinatorics matter.
- Do the actual coordinates matter? No, only the vertex weights.
- Does the answer fit in 32 bits? 48 triangles of at most 10^6 each: yes.
02Brute force
Enumerate every triangulation recursively and sum the triangle weights.
Cost: The number of triangulations is the Catalan number C(n - 2), exponential in n (about 10^26 for n = 50).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.