多边形三角剖分的最低得分
难度:
标签:
题目描述
你有一个凸的 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.length3 <= n <= 501 <= values[i] <= 100
代码结果
运行时间: 54 ms, 内存: 16.0 MB
// Java Stream不适合直接用于动态规划问题的核心逻辑，但我们可以用它来处理输入和输出等辅助工作。
// 思路与Java解法一致。
import java.util.Arrays;
public class Solution {
public int minScoreTriangulation(int[] values) {
int n = values.length;
int[][] dp = new int[n][n];
Arrays.stream(dp).forEach(a -> Arrays.fill(a, Integer.MAX_VALUE));
for (int len = 3; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
for (int k = i + 1; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]);
}
}
}
return dp[0][n - 1];
}
}解释
方法:
这道题目是一个经典的动态规划问题，用于求多边形三角剖分的最低得分。动态规划表f[i][j]表示顶点i到顶点j的多边形剖分的最小得分。初始化f[i][j]为0，因为任何小于3个顶点的多边形不能构成三角形。动态规划的转移方程是：f[i][j] = min(f[i][k] + f[k][j] + v[i] * v[j] * v[k])，其中k从i+1到j-1。这个方程表示在顶点i到顶点j的多边形中，选择一个中间顶点k将多边形分为两部分（i到k和k到j）并加上由顶点i, j和k形成的三角形的得分。我们从小到大计算所有可能的多边形的得分，最终得到整个多边形的最小剖分得分。
时间复杂度:
O(n^3)
空间复杂度:
O(n^2)
代码细节讲解
🦆
在动态规划转移方程中，为什么选择顶点k从i+1到j-1作为中间点进行分割？
▷🦆
动态规划表f初始化为0，但是在分割多边形时如何确保小于3个顶点的情况不被计算？
▷🦆
在实际编码中，如何处理多边形顶点的循环（即顶点是循环数组的情况）？
▷🦆
题解中的动态规划实现是否考虑了所有可能的分割情况，以确保找到最低得分？
▷