题目链接：1039. 多边形三角剖分的最低得分
方法：区间dp
解题思路
区间 DP：最长回文子序列 最优三角剖分【基础算法精讲 22】
代码
回溯写法
class Solution {
public:
int minScoreTriangulation(vector<int>& values) {
int n = values.size();
int cache[n][n]; memset(cache, -1, sizeof(cache));
function<int(int, int)> dfs = [&](int i, int j) -> int {
if (i + 1 == j) return 0;
if (cache[i][j] != -1) return cache[i][j];
int res = INT_MAX;
for (int k = i + 1; k < j; k ++ ) {
res = min(res, dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]);
}
cache[i][j] = res;
return res;
};
return dfs(0, n - 1);
}
};
dp写法（递推）
class Solution {
public:
int minScoreTriangulation(vector<int>& values) {
int n = values.size();
int dp[n][n]; memset(dp, 0, sizeof(dp));
for (int i = n - 3; i >= 0; i -- ) {
for (int j = i + 2; j < n; j ++ ) {
dp[i][j] = INT_MAX;
for (int k = i + 1; k < j; k ++ ) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]);
}
}
}
return dp[0][n - 1];
}
};
复杂度分析
时间复杂度：\(O(n^3)\)；
空间复杂度：\(O(n^2)\)。