本文涉及知识点

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++) {
							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]);
						}

注意：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]一定能枚举到这两种情况。

代码

核心代码

	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++) {
							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]);
						}
					}				
				}
				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);
		}