C++刷LeetCode（1039. 多边形三角剖分的最低得分）【动态规划】

糖逗

题目描述：

1. 给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。
   
2. 
   
3. 假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
   
4. 
   
5. 返回多边形进行三角剖分后可以得到的最低分。
   
6.  
   
7. 
   
8. 示例 1：
   
9. 
   
10. 输入：[1,2,3]
    
11. 输出：6
    
12. 解释：多边形已经三角化，唯一三角形的分数为 6。
    
13. 示例 2：
    
14. 
    
15. 
    
16. 
    
17. 输入：[3,7,4,5]
    
18. 输出：144
    
19. 解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。
    
20. 示例 3：
    
21. 
    
22. 输入：[1,3,1,4,1,5]
    
23. 输出：13
    
24. 解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
    
25.  
    
26. 
    
27. 提示：
    
28. 
    
29. 3 <= A.length <= 50
    
30. 1 <= A[i] <= 100
    
31. 
    
32. 来源：力扣（LeetCode）
    
33. 链接：https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon
    
34. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int minScoreTriangulation(vector<int>& A){
   
4.         int len = A.size();
   
5.         vector<vector<int> >dp(len, vector<int>(len, 0));
   
6.         for(int i = len-3; i >= 0; i--){
   
7.             for(int j = i + 2; j < len; j++){
   
8.                 for(int k = i + 1; k < j; k++){
   
9.                     if(dp[i][j] == 0){
   
10.                         dp[i][j]= A[i]*A[j]*A[k] + dp[i][k] + dp[k][j];
    
11.                     }else{
    
12.                         dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i]*A[j]*A[k]);
    
13.                     }
    
14.                 }
    
15.             }
    
16.         }
    
17.         return dp[0][len-1];
    
18.     }
    
19. };

复制代码

参考链接：https://leetcode-cn.com/problems ... y-njyang-yang-yang/