---
# System prepended metadata

title: 1039. Minimum Score Triangulation of Polygon
tags: [Leetcode, Dynamic Programming, Medium]

---

# 1039. Minimum Score Triangulation of Polygon
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-score-triangulation-of-polygon/description/
## 思路
区间型I DP
思路参考[这里](https://leetcode.com/problems/minimum-score-triangulation-of-polygon/solutions/286705/java-c-python-dp/)
```dp[i][j]``` means the minimum score to triangulate ```A[i] ~ A[j]```,
while there is edge connect ```A[i]``` and ```A[j]```.

We enumerate all points ```A[k]``` with ```i<k<j``` to form a triangle.

The score of this triangulation is ```dp[i][j]```, ```dp[i][k]+dp[k][j]+A[i]*A[j]*A[k]```
## Code
```java=
class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        for(int d=2; d<=n; d++){
            for(int i=0; i+d<n; i++){
                int j = i+d;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k=i+1; k<j; k++){
                    dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k][j]+values[i]*values[k]*values[j]);
                }
            }
        }
        return dp[0][n-1];
    }
}
```