1039. Minimum Score Triangulation of Polygon¶
题目信息¶
- 题号:
1039
- 难度:
Medium
- 主题:
凸多边形、三角剖分、最小总分
- 原题:
- 重点:
顶点按多边形边界顺序给出;三角剖分使用不相交对角线形成
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。