New update is available. Click here to update.

Last Updated: 21 Mar, 2021

Moderate

```
Note that a polygon can be divided into triangles in more than one way. You need to print the minimum sum of triangle values of all the triangles created.
```

```
Given 'N' = 4, Array = [4, 3, 5, 2], the possible scores for these two triangle score are: (3 * 2 * 5) + (3 * 2 * 4) = 54 and (4 * 2 * 5) + (4 * 3 * 5) = 100.
The minimum of these two triangle scores is 54. So you need to print 54.
```

```
The first line contains an integer βTβ which denotes the number of test cases.
The first line of each test case contains a single integer βNβ, denoting the vertices of the polygon.
The next line contains βNβ space-separated integers denoting the value of the vertices of the polygon.
```

```
For each test case, you need to return the minimum triangle score possible from all triangles.
Print the output of each test case in a separate line.
```

```
You donβt need to print anything; It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
3 <= N <= 50
1 <= ARR[i] <= 100
Where 'ARR[i]' denotes the Array elements that represent the sides of the polygon.
Time limit: 1 sec
```

Approaches

We can solve this problem by dividing it into smaller subproblems using recursion. We can divide the polygon recursively into three parts - one triangle and two sub polygons and we have to find the optimal way to divide this so that we will get a minimum triangle score. Let us say the starting and ending index of the given array is βiβ and βjβ , and βkβ is any index between βi+1β and βj-1β then we can divide this polygon into two polygons A[ iβ¦β¦.k] + A[ kβ¦β¦.j] and a triangle formed by vertices i, j and k.

We will recursively divide all the polygons into sub polygons for all possible values of β k β and return the minimum triangle score obtained.

The steps are as follows:

- Let triangleScore('ARR', βiβ, βjβ)
- If there are less than three vertices, we can not make a triangle from them so return 0.
- Run a loop βkβ : βiβ + 1 to βjβ - 1
- Return minimum value of ( INT_MAX ,triangleScore('ARR', βiβ, 'k') + triangleScore('ARR', βkβ, βjβ) + triangleValue of triangle formed by vertices βiβ, βjβ and 'k'.)

We can overcome the problem of solving for the same subarrays multiple times as we had to do in recursion.

Take an example: Array = [1, 2, 3, 4, 5]

This would have two quadrilaterals that need to be further solved: [1, 2, 3, 4] and [2, 3, 4, 5].

[2, 3, 4] in both these quadrilaterals are common, so we can store its result to use them later.

We will simply use a 2-D array βDPβ that would store our previous results and would be visited in order to reduce the calculation time for the subproblems.

The rest of the approach would be the same as in recursion.

The steps are as follows:

- Create a recursive function triangleScore('ARR', βiβ, βjβ).
- Create a 2D vector βDPβ to store results of the subproblems (initialize all values to -1).
- If βDPβ[ i ][ j ] is not equal to β-1β return βDPβ[ i ][ j ].
- Otherwise
- If βjβ < βiβ + 2
- βDPβ[ i ][ j ] = 0.

- Else
- Run a loop βkβ : βi' + 1 to βjβ - 1
- = INT_MAX
- βDP[i][j]β = minimum value of (INT_MAX, triangleScore('ARR', βiβ, βkβ) + triangleScore('ARR', βkβ, βjβ) + triangleValue of triangle formed by vertices βi', βjβ and βkβ).

- If βjβ < βiβ + 2
- Return βDPβ[ i ][ j ].

The idea is to take each pair of vertices possible and then with those fixed, find a vertex in between such that the polygon on the left and right side of it is of min score.

The steps are as follows:

** **

- Create a 2d βDPβ array that will store the minimum triangulation score of the polygon with vertices starting from βiβ..'j' and there is an edge between βiβ and βjβ
- start swiping each vertex using index 'i' and use the index 'j' to keep the other end fixed:
- This βiβ and βjβ edge will then be evaluated with every other vertex in between them by making a triangle with it and checking the score of the left and right side of the remaining polygon.

- Return the minimum triangle score.