Cheapest Way to Cut a Polygon

Medium

You have a convex polygon whose vertices carry integer labels; labels[i] is the label of the i-th vertex going clockwise. A polygon with n vertices must be cut along non-crossing diagonals into n − 2 triangles. A triangle costs the product of its three vertex labels, and the cost of the whole cut is the sum over all triangles. Return the lowest possible cost.

Example 1

labels=[2, 5, 3] → 30

It is already a triangle: 2 · 5 · 3 = 30.

Example 2

labels=[1, 6, 2, 6] → 24

The diagonal between the vertices labelled 1 and 2 gives 1 · 6 · 2 + 1 · 2 · 6 = 24; the other diagonal would cost 1 · 6 · 6 + 6 · 2 · 6 = 108.

Example 3

labels=[4, 1, 4, 1, 4] → 24

Constraints

3 ≤ len(labels) ≤ 50
1 ≤ labels[i] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

labels=[2, 5, 3]

Expected

Run checks the first 3 tests in your browser. Submit checks all 94 tests on the server, hidden ones included.