题目及示例
你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。
假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。
返回 多边形进行三角剖分后可以得到的最低分 。
示例 1：
输入：values = [1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。
示例 2：
输入：values = [3,7,4,5]
输出：144
解释：有两种三角剖分，可能得分分别为：3 * 7 * 5 + 4 * 5 * 7 = 245，或 3 * 4 * 5 + 3 * 4 * 7 = 144。最低分数为 144。
示例 3：
输入：values = [1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 1 * 1 * 3 + 1 * 1 * 4 + 1 * 1 * 5 + 1 * 1 * 1 = 13。
提示：
n == values.length
3 <= n <= 50
1 <= values[i] <= 100
解题思路
题目主要考察的动态规划思想
假设dp(i,j)(i>=j+2)是一个由 i ,i+1 … j-1,j构成的凸的 n 边形
我们对其进行遍历，取当前遍历的中间点k，并进行剖分
这时凸的 n 边形就则变成了三部分
1.由i,i+1 … k-1,k构成的凸的 n 边形
2.由i,k,j构成的三角形
3.由k,k+1 … j-1,j构成的凸的 n 边形
通过遍历求并求和找出三部分和的最小数
关于1和3部分我们可以用同样方法再次剖分
一直剖分到为三角形为止，即当前的 i+2 = j
代码展示
var minScoreTriangulation = function (values) {
const n = values.length
const map = new Map()
const dp = (i, j) => {
if (i + 2 > j) {
return 0
}
if (i + 2 == j) {
return values[i] * values[i + 1] * values[j]
}
const key = i + j * n
if (!map.has(key)) {
let min = Number.MAX_VALUE
for (let k = i + 1; k < j; k++) {
min = Math.min(min, values[i] * values[k] * values[j] + dp(i, k) + dp(k, j))
}
map.set(key, min)
}
return map.get(key)
}
return dp(0, n - 1)
}
