Leetcode 1039. 多边形三角形剖分的最低得分 枚举型区间dp C++实现

问题：Leetcode 1039. 多边形三角形剖分的最低得分

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

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

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

算法1：记忆化搜索

时间复杂度：O(n³) 。其中 n 为 values 的长度。动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题中状态个数等于 O(n²) ，单个状态的计算时间为 O(n) ，因此时间复杂度为 O(n³) 。
空间复杂度：O(n²) 。保存多少状态，就需要多少空间。

代码：

class Solution {
public:int minScoreTriangulation(vector<int>& values) {int n = values.size();vector<vector<int>> memo(n,vector<int>(n,-1));auto dfs = [&](auto &&dfs,int i,int j) -> int{if(i + 1 == j)  return 0;//只有两条边，不能构成三角形0int &res = memo[i][j];if(res != -1)   return res;//被计算过res = INT_MAX;for(int k = i + 1;k < j;k++)res = min(res,dfs(dfs,i,k) + dfs(dfs,k,j) + values[i] * values[j] * values[k]);return res;};return dfs(dfs,0,n - 1);}
};

---

算法2：1:1 翻译成递推

把 dfs 改成 dp 数组，把递归改成循环就好了。相当于原来是用递归计算每个状态 ( i  , j ) ，现在改用循环去计算每个状态 ( i , j ) 。

状态转移方程和递归完全一致：

需要注意循环的顺序：

由于 i < k ，dp [ i ] 要能从 dp [ k ] 转移过来，必须先计算出 dp [ k ]，所以 i 要倒序枚举；
由于 j > k ，dp [ i ] [ j ] 要能从 dp [ i ] [ k ] 转移过来，必须先计算出 dp [ i ] [ k ] ，所以 j 要正序枚举。

时间复杂度：O(n³) 。其中 n 为 values 的长度。动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题中状态个数等于 O(n²) ，单个状态的计算时间为 O(n) ，因此时间复杂度为 O(n³) 。

空间复杂度：O(n²) 。有 O(n²) 个状态。

代码：

class Solution {
public:int minScoreTriangulation(vector<int>& values) {int n = values.size();vector<vector<int>> dp(n,vector<int>(n));for(int i = n - 3;i >= 0;i--){for(int j = i + 2;j < n;j++){dp[i][j] = INT_MAX;for(int k = i + 1;k < j;k++)dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);}}return dp[0][n - 1];}
};