#199HardDynamic Programming· Interval DP

Cheapest Polygon Triangulation

A 3D-modelling tool must split a convex polygon with `n` corners into `n - 2` triangles by drawing non-crossing diagonals between corners. Each corner carries a positive integer weight, given in order around the polygon. The **cost** of one triangle is the product of the weights of its three corners, and the cost of a triangulation is the sum of the costs of all its triangles. Return the minimum possible cost over all ways to triangulate the polygon.

Input format

`weights`: an array of `n` positive integers, the corner weights in order around the polygon.

Output format

An integer: the minimum total triangulation cost.

Examples

Input: weights = [1, 2, 3]

Output: 6

A triangle is its own triangulation: 1 * 2 * 3 = 6.

Input: weights = [3, 7, 4, 5]

Output: 144

Splitting along the diagonal between corners with weights 3 and 4 gives 3*7*4 + 3*4*5 = 144; the other diagonal gives 3*7*5 + 7*4*5 = 245.

Input: weights = [1, 3, 1, 4, 1, 5]

Output: 13

Cutting off corners next to the weight-1 vertices keeps every triangle cheap; the best total is 13.

Constraints

3 <= n <= 100
1 <= weights[i] <= 100

#dynamic-programming
#interval-dp
#geometry
#recursion