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

本文涉及知识点

C++动态规划 数学
LeetCode1039. 多边形三角剖分的最低得分

你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，此中 values 是第 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 <= 100
动态规划

动态规划的状态表现

dp[ct] 表现 端点：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

1. for (int j = i + 1; j < i + ct-1; j++) {
2.                                                         const int c1 = j - i + 1;
3.                                                         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]);
4.                                                 }

复制代码

注意：i到i+ct-1一定是连续的，i+ct-1到i不一定连续，即：(i+ct)%N 不一定等于i,故只能拆一个三角形出来，不能拆一条线。
单个状态转移的时间复杂度：O(n) 总时间复杂度：O(nnn)
动态规划的初始值

dp[3] = values*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] + dp[N-1][i+2]一定能罗列到这两种环境。
代码

核心代码

1.         class Solution {                public:                        int minScoreTriangulation(vector<int>& values) {                                const int 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++) {
2.                                                         const int c1 = j - i + 1;
3.                                                         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]);
4.                                                 }
5.                                         }                                                                }                                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;                        }                };

复制代码

单位测试

1. vector<int> values;
2.                 TEST_METHOD(TestMethod11)
3.                 {
4.                         values = { 1, 2, 3 };
5.                         auto res = Solution().minScoreTriangulation(values);
6.                         AssertEx(6, res);
7.                 }
8.                 TEST_METHOD(TestMethod12)
9.                 {
10.                         values = { 3,7,4,5 };
11.                         auto res = Solution().minScoreTriangulation(values);
12.                         AssertEx(144, res);
13.                 }
14.                 TEST_METHOD(TestMethod13)
15.                 {
16.                         values = { 1,3,1,4,1,5 };
17.                         auto res = Solution().minScoreTriangulation(values);
18.                         AssertEx(13, res);
19.                 }

复制代码

扩展阅读

我想对各人说的话工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作有效学习：明确的目的 实时的反馈 拉伸区（难度符合） 专注闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。假如步伐是一条龙，那算法就是他的是睛失败+反思=成功 成功+反思=成功 视频课程

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

操作体系：win7 开发环境： VS2019 C++17
大概 操作体系：win10 开发环境： VS2022 C++17
如无特别说明，本算法用**C++**实现。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。