数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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 := 0，j := l – 1，当 j < n 时，将 i 和 j 增加 1
对于范围从 i + 1 到 j – 1 的 k
如果 dp[i, j] = 0，则
dp[i, j] := inf 和 dp[i, k] + dp[k, j] + A[i] * A[j] * A[k] 的最小值
否则 dp[i, j] := dp[i,j] 和 dp[i, k] + dp[k, j] + A[i] * A[j] * A[k] 的最小值
返回 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
更新于：2020年4月30日
277 次查看
广告