[DAY16] 1039. Minimum Score Triangulation of Polygon

2025 iThome 鐵人賽

DAY 16

自我挑戰組

Leetcode 小白練功坊系列第 16 篇

17th鐵人賽

hesta

2025-09-29 23:34:18

9 瀏覽

分享至

題目連結(https://leetcode.com/problems/minimum-score-triangulation-of-polygon/?envType=daily-question&envId=2025-09-29)

You have a convex n-sided polygon where each vertex has an integer value. You are given an integer array values where values[i] is the value of the ith vertex in clockwise order.

Polygon triangulation is a process where you divide a polygon into a set of triangles and the vertices of each triangle must also be vertices of the original polygon. Note that no other shapes other than triangles are allowed in the division. This process will result in n - 2 triangles.

You will triangulate the polygon. For each triangle, the weight of that triangle is the product of the values at its vertices. The total score of the triangulation is the sum of these weights over all n - 2 triangles.

Return the minimum possible score that you can achieve with some **triangulation **of the polygon.

今天也是每日一題，雖然沒跟三角形直接相關，但也是幾何題，最近好像和三角形特別有緣>< 不過我覺得這題要聯想出 DP的模式需要好好思考一下，給大家錯誤想法參考～

1. Repeat（題目重複確認）

輸入：整數陣列 values
輸出：凸多邊形三角分割後，n-2個三角形的最小乘積
前提：
- n == values.length
- 3 <= n <= 50
- 1 <= values[i] <= 100

2. Examples（舉例確認理解）

Input: values = [3,7,4,5]

Output: 144

Explanation: There are two triangulations, with possible scores: 3 * 7 * 5 + 4 * 5 * 7 = 245, or 3 * 4 * 5 + 3 * 4 * 7 = 144.

The minimum score is 144.

3. Approach（解題思路）

方法：區間 DP

dp[i][j] 表示將頂點 i 到 j 這段多邊形剖分的最小成本
對於區間 [i, j]，我們列舉中間的頂點 k，將多邊形分成三部分：
- 三角形 (i, k, j) 的成本：values[i] * values[k] * values[j]
- 左邊小多邊形 [i, k] 的成本：dp[i][k]
- 右邊小多邊形 [k, j] 的成本：dp[k][j]
時間複雜度: O(n³) - 三層循環
空間複雜度: O(n²) - dp 陣列

4. Code（C++）

＃錯誤寫法
class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        sort(values.begin(), values.end());
        int n = values.size();

        vector<int> dp(n+1);
        dp[3] = values[0]*values[1]*values[2];
        for(int i = 4; i <= n; i++){
            dp[i] = dp[i-1] + (values[i-1]*values[0]*values[1]);
        }
        return dp[n];
    }
};

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        //len 是頂點數
        for(int len = 3; len <= n; len++){
            //i 是起點
            for(int i = 0; i + len - 1 < n; i++){
                int j = i + len - 1; //j是終點
                dp[i][j] = INT_MAX; // dp[i][j] 表示從頂點 i 到頂點 j 的多邊形三角形分割的最小成本
                //k 是中間的頂點
                for(int k = i+1; k < j; k++){ 
                    // 三角形 (i, k, j) + 左邊多邊形 [i, k] + 右邊多邊形 [k, j]
                    int cost = dp[i][k]+ dp[k][j]+ values[i]*values[j]*values[k];
                    dp[i][j] = min(dp[i][j], cost);
                }
            }
        }
        return dp[0][n-1];
    }
};

5. Test 範例

多邊形頂點順序：

      1(7)

     /    \
0(3)       2(4)
     \    /

      3(5)

dp[0][3] 表示整個多邊形 [0,1,2,3] 的最小代價

枚舉中間頂點 k:

k=1: 三角形(0,1,3) + dp[0][1] + dp[1][3]

= 3 * 7 * 5 + 0 + (7 * 4 * 5)

= 105 + 140 = 245

k=2: 三角形(0,2,3) + dp[0][2] + dp[2][3]

= 3 * 4 * 5 + (3 * 7 * 4) + 0

= 60 + 84 = 144 ← 最小值!

6. 相關題目與延伸概念

和此題教科書出現過的常見案例概念相同

Matrix_chain multiplication(括號法讓乘法次數最少)

時間：O(n^3)，想法：三層迴圈->n^3

for len = 2 to n

for i = 1 to n-len+1

for k = i to j-1

Matrix-chain(p)
		let s[1...n, 1...n], c[1...n-1, 2...n]
		//s[i,j]計算 AiAi+1...Aj 所需最少純量乘法次數
		for i = 1 to n
				s[i,i] = 0
				for len = 2 to n
						for i = 1 to n-len+1
								j = i+len-1
								s[i,j] = s[i,i]+s[i+1,j]+p[i-1]p[i]p[j]
								for k = i to j-1
									r = s[i,k]+s[k+1,j]+p[i-1]p[k]p[j]
									if r < s[i,j]
											s[i,j] = r
											c[i,j] = k
					return s and c
				
Print-Parens(c,i,j) //c[i,j]輸出最佳括號位置
		if i == j
			print "A"
		else
			print "("
			Print-Parens(c,i,c[i,j])
			Print-Parens(c,c[i,j]+1,j)
			print ")"