1039. 多边形三角剖分的最低得分
你有一个凸的 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解答：这段代码使用动态规划来解决「分割多边形 II」问题，其思路与「钢条切割问题」类似。
具体来说，我们枚举三角形的边数，然后枚举起点和终点，最后枚举第三个点的位置，计算得分并更新最小得分。对于边数为 3 的三角形，我们可以直接计算得分。
在代码中，我们使用一个二维数组 dp 来保存子问题的最小得分。其中，dp[i][j] 表示将点 i 到点 j 的多边形进行三角剖分的最小得分。对于每个子问题，我们可以通过枚举第三个点的位置来计算得分并更新最小得分。
最后，返回 dp[0][n - 1] 即可得到整个多边形的最小得分。
class Solution {
public int minScoreTriangulation(int[] w) {
int n = w.length;
int[][] dp = new int[n][n];
// 枚举三角形边数
for (int len = 3; len <= n; len++) {
// 枚举起点
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (len == 3) {
// 当只有三个点时，直接计算得分
dp[i][j] = w[i] * w[j] * w[i + 1];
} else {
// 初始化得分为极大值
dp[i][j] = (int)1e9;
// 枚举第三个点的位置，更新最小得分
for (int k = i + 1; k <= j - 1; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + w[i] * w[k] * w[j]);
}
}
}
}
return dp[0][n - 1];
}
}
