> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/minimum-score-triangulation-of-polygon.md).

# Minimum Score Triangulation of Polygon

Given `N`, consider a convex `N`-sided polygon with vertices labelled `A[0], A[i], ..., A[N-1]` in clockwise order.

Suppose you triangulate the polygon into `N-2` triangles.  For each triangle, the value of that triangle is the **product** of the labels of the vertices, and the *total score* of the triangulation is the sum of these values over all `N-2` triangles in the triangulation.

Return the smallest possible total score that you can achieve with some triangulation of the polygon.

1.

**Example 1:**

```
Input: [1,2,3]
Output: 6
Explanation: The polygon is already triangulated, and the score of the only triangle is 6.
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2019/05/01/minimum-score-triangulation-of-polygon-1.png)

```
Input: [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.
```

**Example 3:**

```
Input: [1,3,1,4,1,5]
Output: 13
Explanation: The minimum score triangulation has score 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.
```

**Note:**

1. `3 <= A.length <= 50`
2. `1 <= A[i] <= 100`

## Intuition

If we pick a side of our polygon, it can form `n - 2` triangles. Each such triangle forms 2 sub-polygons. We can analyze `n - 2` triangles, and get the minimum score for sub-polygons using the recursion.\
\
This is how this procedure looks for a sub-polygon (filled with diagonal pattern above).

![](https://assets.leetcode.com/users/votrubac/image_1557470819.png)

![](https://assets.leetcode.com/users/votrubac/image_1557471328.png)

```java
class Solution {
    public int minScoreTriangulation(int[] A) {
        int n = A.length;
        if (n <= 2)
            return 0;
        int dp[][] = new int[n][n];
        // 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.
        // We will have diagonal base case when i==j, then ans is not possible
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                // Choosing all the points between i & j as first triangle
                for (int k = i + 1; k < j; k++)
                    dp[i][j] = Math.min(dp[i][j] == 0 ? Integer.MAX_VALUE : dp[i][j],
                            dp[i][k] + A[i] * A[k] * A[j] + dp[k][j]);
            }
        }
        return dp[0][n - 1];
    }
}
```