【C++动态规划 数学】1039. 多边形三角剖分的最低得分|2130

本文涉及知识点

C++动态规划 数学

LeetCode1039. 多边形三角剖分的最低得分

你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。

假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。

返回 多边形进行三角剖分后可以得到的最低分 。

示例 1：

输入：values = [1,2,3]

输出：6

解释：多边形已经三角化，唯一三角形的分数为 6。

示例 2：

输入：values = [3,7,4,5]

输出：144

解释：有两种三角剖分，可能得分分别为：375 + 457 = 245，或 345 + 347 = 144。最低分数为 144。

示例 3：

输入：values = [1,3,1,4,1,5]

输出：13

解释：最低分数三角剖分的得分情况为 113 + 114 + 115 + 111 = 13。

提示：

n == values.length

3 const int c1 = j - i + 1; dp[ct][i] = min(dp[ct][i],dp[c1][i] + dp[ct+1-c1][(j)%N] + values[i]* values[(i+ct-1)%N]* values[j%N]); } public: int minScoreTriangulation(vector const int N = values.size(); vector dp[3][i] = values[i] * values[(i + 1) % N] * values[(i + 2) % N]; } for (int ct = 4; ct