C ++中多边形的最小分数三角剖分
假设我们有一个值N，请考虑一个凸N边的多边形，其顶点分别标记为A[0]，A[i]，...，A[N-1]为顺时针方向。现在假设我们想将多边形分成N-2个三角形。对于每个三角形，该三角形的值是顶点标签的乘积，并且三角剖分的总得分将是三角剖分中所有N-2个三角形上这些值的总和。我们必须找到通过多边形的三角剖分可以达到的最小总分。因此，如果输入为[1,2,3]，则输出将为6，因为已对多边形进行了三角测量，唯一三角形的分数为6。
为了解决这个问题，我们将遵循以下步骤-
创建大小为50x50的矩阵dp，并用0填充
n：=给定数组的大小
对于n到n范围内的l
对于范围i+1至j–1的k
dp[i，j]：=inf和dp[i，k]的最小值+dp[k，j]+A[i]*A[j]*A[k]
如果dp[i，j]=0，则
否则dp[i，j]：=dp[i，j]和dp[i，k]+dp[k，j]+A[i]*A[j]*A[k]的最小值
对于i：=0，j：=l–1，当j<n时，将i和j加1
返回dp[0，n–1]
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int minScoreTriangulation(vector<int>& A) {
lli dp[50][50];
for(int i = 0; i < 50; i++){
for(int j = 0; j < 50; j++){
dp[i][j] = 0;
}
}
int n = A.size();
for(int l = 3; l <= n; l++){
for(int i = 0, j = l - 1; j < n;i++, j++){
for(int k = i + 1; k < j; k++){
dp[i][j] = min(dp[i][j] == 0?INT_MAX : dp[i][j],
dp[i][k] + dp[k][j] + A[i] * A[k] * A[j]);
}
}
}
return dp[0][n - 1];
}
};
main(){
vector<int> v1 = {1,2,3};
Solution ob;
cout << (ob.minScoreTriangulation(v1));
}输入值
[1,2,3]
输出结果
6