LeetCode--1039

Smiling-Weeping / 2023-08-12 / 原文

Smiling & Weeping

　　　　　　　　　　　　　　　　　　----我总是躲在梦与季节的身处，

　　　　　　　　　　　　　　　　　　　　　　听花与黑夜唱尽梦魇，

　　　　　　　　　　　　　　　　　　　　唱尽繁华，唱断所有记忆的来路。

题目链接：1039. 多边形三角剖分的最低得分 - 力扣（LeetCode）

题目描述：

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

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

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

思路：简单的区间DP，长度最小为3（初始len=3），然后上模板

Talk is cheap , show me the code

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