 New update is available. Click here to update.
Last Updated: 21 Mar, 2021
##### Minimum Score
Moderate
Problem statement #### Now, you need to find the minimum total triangle score. The total triangle score is the sum of the triangle scores of all the possible triangles.

##### Note:
``````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.
``````
##### Example :
``````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.
`````` ##### Input Format:
``````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.
``````
##### Output Format:
``````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.
``````
##### Note:
``````You don’t need to print anything; It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````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

## 01Approach 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’) be our recursive function where ‘i’ and ‘j’ are the starting and ending index of vertices of the polygon.
• 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'.) 