C++刷LeetCode（1039. 多边形三角剖分的最低得分）【动态规划】
题目描述：给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A, A, ..., A。
假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分。
示例 1：
输入：
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。
示例 2：
输入：
输出：144
解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。
示例 3：
输入：
输出：13
解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
提示：
3 <= A.length <= 50
1 <= A <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int minScoreTriangulation(vector<int>& A){
int len = A.size();
vector<vector<int> >dp(len, vector<int>(len, 0));
for(int i = len-3; i >= 0; i--){
for(int j = i + 2; j < len; j++){
for(int k = i + 1; k < j; k++){
if(dp == 0){
dp= A*A*A + dp + dp;
}else{
dp = min(dp, dp + dp + A*A*A);
}
}
}
}
return dp;
}
};
参考链接：https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon/solution/qu-jian-dong-tai-gui-hua-4ms-by-njyang-yang-yang/
页:
[1]