小程序模板素材,深圳搜狗seo,网页制作教程哔哩,广告网站搭建文章目录1. 题目2. 解题1. 题目
给定 N#xff0c;想象一个凸 N 边多边形#xff0c;其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。
假设您将多边形剖分为 N-2 个三角形。 对于每个三角形#xff0c;该三角形的值是顶点标记的乘积#xff0c;三角剖分的分数是…
文章目录1. 题目2. 解题1. 题目
给定 N想象一个凸 N 边多边形其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。
假设您将多边形剖分为 N-2 个三角形。 对于每个三角形该三角形的值是顶点标记的乘积三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分。
示例 1
输入[1,2,3]
输出6
解释多边形已经三角化唯一三角形的分数为 6。示例 2输入[3,7,4,5]
输出144
解释有两种三角剖分
可能得分分别为3*7*5 4*5*7 245
或 3*4*5 3*4*7 144。
最低分数为 144。示例 3
输入[1,3,1,4,1,5]
输出13
解释最低分数三角剖分的得分情况为
1*1*3 1*1*4 1*1*5 1*1*1 13。提示
3 A.length 50
1 A[i] 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 1130. 叶值的最小代价生成树区间DP/单调栈贪心
dp[i][j] 表示区间 [i,j] 所有组成的三角形得分之和的最小值区间长度从 3 开始往上变大状态转移方程为 dp[i][j]min(dp[i][j],dp[i][k]A[i]∗A[k]∗A[j]dp[k][j])dp[i][j] min(dp[i][j], dp[i][k]A[i]*A[k]*A[j]dp[k][j])dp[i][j]min(dp[i][j],dp[i][k]A[i]∗A[k]∗A[j]dp[k][j])k 取值 [i1, j-1]
class Solution {
public:int minScoreTriangulation(vectorint A) {int n A.size(), len, i, j, k;vectorvectorint dp(n, vectorint(n, 0));for(len 3; len n; len){for(i 0; i n; i){j ilen-1;if(j n) continue;dp[i][j] INT_MAX;for(k i1; k j; k){dp[i][j] min(dp[i][j], dp[i][k]A[i]*A[k]*A[j]dp[k][j]);}}}return dp[0][n-1];}
};8 ms 8.8 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
