題目描述
給定 N忌警，想象一個(gè)凸 N 邊多邊形绰沥，其頂點(diǎn)按順時(shí)針順序依次標(biāo)記為 A[0], A[i], ..., A[N-1]筷转。
假設(shè)您將多邊形剖分為 N-2 個(gè)三角形筐喳。對(duì)于每個(gè)三角形催式，該三角形的值是頂點(diǎn)標(biāo)記的乘積，三角剖分的分?jǐn)?shù)是進(jìn)行三角剖分后所有 N-2 個(gè)三角形的值之和避归。
返回多邊形進(jìn)行三角剖分后可以得到的最低分荣月。
題目解析
- 多個(gè)三角形可以拼接成一個(gè)多邊形，所以一個(gè)凸N邊形可分解為兩個(gè)凸多變形加一個(gè)三角形梳毙，所以子集的最優(yōu)解可以合并為全局最優(yōu)解哺窄。
- 構(gòu)建dp[i][j] 表示從i～j的三角形最優(yōu)值，所以dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[I]A[j]A[k]) 其中k∈[i+1, j-1]账锹，可以使用dfs+記憶化搜索萌业，最終返回dp[0][A.size()-1]
- 記得處理三角形的特殊情況。
C++代碼
class Solution {
public:
int dp[105][105];
int arr[105];
int dfs(int s, int e) {
if(e - s <=1) return 0;
if(dp[s][e] != -1) return dp[s][e];
int maxTemp = 9999999;
for(int i = s + 1; i <= e -1; i++) {
maxTemp = min(maxTemp, dfs(s, i) + dfs(i, e) + arr[s] * arr[i] * arr[e]);
}
dp[s][e] = maxTemp;
return dp[s][e];
}
int minScoreTriangulation(vector<int>& A) {
if(A.size() < 4) {
int ans = 1;
for(int i = 0; i < A.size(); i++) {
ans *= A[i];
}
return ans;
}
for(int i = 0; i < A.size(); i++) {
arr[i] = A[i];
}
memset(dp, -1, sizeof(dp));
return dfs(0, A.size() - 1);
}
};
