資料結構
網路
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 次檢視
廣告