假设我们有一个值N,请考虑一个凸N边的多边形,其顶点分别标记为A [0],A [i],...,A [N-1]为顺时针方向。现在假设我们想将多边形分成N-2个三角形。对于每个三角形,该三角形的值是顶点标签的乘积,并且三角剖分的总得分将是三角剖分中所有N-2个三角形上这些值的总和。我们必须找到通过多边形的三角剖分可以达到的最小总分。因此,如果输入为[1,2,3],则输出将为6,因为已对多边形进行了三角测量,唯一三角形的分数为6。
为了解决这个问题,我们将遵循以下步骤-
创建大小为50 x 50的矩阵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