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