C ++中多边形的最小分数三角剖分

假设我们有一个值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