# 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/)

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

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];
}
}