1039. Minimum Score Triangulation of Polygon

题目信息

题号:

1039

难度:

Medium

主题:

凸多边形、三角剖分、最小总分

原题:

LeetCode 1039

重点:

顶点按多边形边界顺序给出;三角剖分使用不相交对角线形成 n - 2 个三角形,每个三角形得分为三个顶点值的乘积

题目重述

给定凸多边形各顶点的整数值数组 values,数组顺序与顶点沿边界的顺序一致。可以在非相邻顶点之间添加互不交叉的对角线,把多边形完整划分为三角形。

每个三角形的得分等于它三个顶点值的乘积,一次完整剖分的总分是所有三角形得分之和。请返回所有合法三角剖分中的最小总分。

3 <= values.length <= 50,1 <= values[i] <= 100。

自建示例

四边形只有两种三角剖分:

输入:values = [1,2,3,4]
输出:18
解释:连接顶点 0 和 2 时得分为 1*2*3 + 1*3*4 = 18;另一条对角线产生 1*2*4 + 2*3*4 = 32,因此最小值为 18。

多边形本身就是三角形:

输入:values = [2,3,5]
输出:30
解释:三个顶点只能形成唯一三角形,得分为 2 * 3 * 5 = 30。