1039. Minimum Score Triangulation of Polygon ============================================ 题目信息 -------- :题号: 1039 :难度: Medium :主题: 凸多边形、三角剖分、最小总分 :原题: `LeetCode 1039 `_ :重点: 顶点按多边形边界顺序给出;三角剖分使用不相交对角线形成 ``n - 2`` 个三角形,每个三角形得分为三个顶点值的乘积 题目重述 -------- 给定凸多边形各顶点的整数值数组 ``values``,数组顺序与顶点沿边界的顺序一致。可以在非相邻顶点之间添加互不交叉的对角线,把多边形完整划分为三角形。 每个三角形的得分等于它三个顶点值的乘积,一次完整剖分的总分是所有三角形得分之和。请返回所有合法三角剖分中的最小总分。 ``3 <= values.length <= 50``,``1 <= values[i] <= 100``。 自建示例 -------- 四边形只有两种三角剖分: .. code-block:: text 输入:values = [1,2,3,4] 输出:18 解释:连接顶点 0 和 2 时得分为 1*2*3 + 1*3*4 = 18;另一条对角线产生 1*2*4 + 2*3*4 = 32,因此最小值为 18。 多边形本身就是三角形: .. code-block:: text 输入:values = [2,3,5] 输出:30 解释:三个顶点只能形成唯一三角形,得分为 2 * 3 * 5 = 30。