【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 <= n <= 50
1 <= values[i] <= 100

动态规划

动态规划的状态表示

dp[ct] [i]表示 端点：i,(i+1)%n,(i+2)%n,(i+3)%n ⋯ \cdots ⋯ (i+n-1)%n 组成的多边形的最小分数。
cnt < 3，无意义。空间复杂度：O(nn)

动态规划的填表顺序

ct = 4 to n 枚举后置状态

动态规划的转移方程

对 ∀ \forall ∀ ct,i

for(int j = i +1; j < i + ct-1; j++){constint 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]);}

注意：i到i+ct-1一定是连续的，i+ct-1到i不一定连续，即：(i+ct)%N 不一定等于i,故只能拆一个三角形出来，不能拆一条线。

单个状态转移的时间复杂度：O(n) 总时间复杂度：O(nnn)

动态规划的初始值

dp[3][i] = values[i]*values[(i+1)%n]*values[(i+2)%n]
dp[2] 等于0

动态规划的返回值

任意边一定和顺时针的临边或逆时针的临边组成三角型。
以边i,i+1 比例，要么是 i ,i+1,i+2， 要么是i-1,i,i+1。我们枚举：
dp[3][i] + dp[N-1][i+2]一定能枚举到这两种情况。

代码

核心代码

classSolution{public:intminScoreTriangulation(vector<int>& values){constint N = values.size(); vector<vector<int>>dp(N+1,vector<int>(N, INT_MAX /2)); dp[2].assign(N,0);for(int i =0; i < N; i++){ dp[3][i]= values[i]* values[(i +1)% N]* values[(i +2)% N];}for(int ct =4; ct < N; ct++){for(int i =0; i < N; i++){for(int j = i +1; j < i + ct-1; j++){constint 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]);}}}int ans = INT_MAX;for(int i =0; i < N; i++){ ans =min(ans, dp[3][i]+ dp[N-1][(i +2)% N]);}return ans;}};

单元测试

vector<int> values;TEST_METHOD(TestMethod11){ values ={1,2,3};auto res =Solution().minScoreTriangulation(values);AssertEx(6, res);}TEST_METHOD(TestMethod12){ values ={3,7,4,5};auto res =Solution().minScoreTriangulation(values);AssertEx(144, res);}TEST_METHOD(TestMethod13){ values ={1,3,1,4,1,5};auto res =Solution().minScoreTriangulation(values);AssertEx(13, res);}

扩展阅读

视频课程

先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。