文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定 N，想象一個凸 N 邊多邊形，其頂點按順時針順序依次標記為 A[0], A[i], ..., A[N-1]。

假設您將多邊形剖分為 N-2 個三角形。
對于每個三角形，該三角形的值是頂點標記的乘積，三角剖分的分數是進行三角剖分后所有 N-2 個三角形的值之和。

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

示例 1： 輸入：[1,2,3] 輸出：6 解釋：多邊形已經三角化，唯一三角形的分數為 6。 示例 2：

輸入：[3,7,4,5] 輸出：144 解釋：有兩種三角剖分， 可能得分分別為：3*7*5 + 4*5*7 = 245， 或 3*4*5 + 3*4*7 = 144。 最低分數為 144。示例 3： 輸入：[1,3,1,4,1,5] 輸出：13 解釋：最低分數三角剖分的得分情況為 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。提示： 3 <= A.length <= 50 1 <= A[i] <= 100

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
LeetCode 1130. 葉值的最小代價生成樹（區間DP/單調棧貪心）

• dp[i][j] 表示區間 [i,j] 所有組成的三角形得分之和的最小值
• 區間長度從 3 開始往上變大
• 狀態轉移方程為 $dp[i][j]=min(dp[i][j],dp[i][k]+A[i]?A[k]?A[j]+dp[k][j])$，k 取值 [i+1, j-1]

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

8 ms 8.8 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1039. 多边形三角剖分的最低得分（区间DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。