In this problem you are given an array of integers, which represents the vertices of an N-sided convex polygon in clockwise order. You have to triangulate the given polygon into N-2 triangles.

The value of a triangle is the product of the labels of vertices of that triangle. The total score of the triangulation is the sum of the value of all the triangles.

All you have to do is find the minimum score of the triangulation of the given polygon. For example:

Sample Input: 3

1 2 3

Sample Output: 6

HOW?

The polygon is already triangulated, and the score of the only triangle is 1x2x3 = 6.

Sample Input: 4

2 3 1 4

Sample Output: 14

HOW?

The polygon can be triangulated in 2 ways. The first way score is 14 and the second way score is 36. Minimum score is 14.

For more clarity of the question, watch below part of the video.


Moving On:

• In this problem we need to find the minimum score of triangulation of a given polygon.
• We have already learned how we can explore all the possible ways of triangulation in a polygon in the previous problem. This problem involves a similar concept.
• To start with, let's take a look at the above example (for n = 4) once again.





• So over here to consider all the ways of triangulation we fixed i and j in the polygon and varied k.
• Then corresponding to each variation of k, we calculated the score.
• And finally the result will be the minimum of both the scores.
• In order to solve this problem we will use the Gap Strategy of dynamic programming.
  
  1. In this strategy we use a 2D array of n x n and then we assign some meaning to the cells of the 2D array.
  2. Then we fill the matrix diagonally, moving from smaller problems to the bigger problem.
• Let's try to draw and fill the dp matrix for n = 4 for arbitrary values of vertices say a, b, c and d.





• In the dp, rows will correspond to the first vertex which is fixed (i) and columns correspond to the second vertex which is fixed (j) of the polygon (or sub-polygon).
• So at any cell we store the minimum score of triangulation of the sub-polygon that starts with ith vertex and ends with jth vertex in clockwise direction.





• For example; at i = b and j = d, the matrix will store the minimum score of triangulation of sub-polygon starting from vertex b and ending on vertex c (in clockwise direction).





• In this case dp at i = b and j = d will store (b*c*d) as this is the only possible triangulation.
• The lower triangular part of the matrix will be irrelevant.





• Now talking of the first relevant diagonal; this diagonal represents the scenario, if there were only one vertex in a sub polygon, so what do you think would be the minimum score in this case?
• Yeah right, it will be zero as no triangulation is possible and therefore no score.





• Second diagonal is also dealt in the same way. As there will be no triangulations possible so the cost will also be zero.





• Moving to the next diagonal; we see that this diagonal represents a sub polygon with three vertices. So it means that the polygon is already triangulated. Therefore this diagonal will store the product of values corresponding to each vertex.





• In the next diagonal, we have only one cell which will store the final result of our problem.
• And we know that to calculate the minimum score of triangulation of a quadrilateral, we have to consider 2 possibilities.





• So to calculate the score of a quadrilateral we can take the help of dp filled so far. Looking at the first case in the above figure, we need a minimum score of adc, abc and cd (cd might have no relevance in this case but we have just used to build a pattern which will be used for a bigger value of n(s)).
• Okay, so what we can do is; use the value of abc and cd from the dp matrix and calculate the value for adc which at this moment will be the product of ith, jth and kth value of array which in this case are 'a', 'd' and 'c', so we take their product.
• Similar efforts will be made for the second scenario.
• And the minimum of both these values will be stored at dp[abcd] (dp[3][3]; which is the final result for this problem).
For more clarity of this part; watch below part of the video.


Let's try to code this!





1. To start with, define a 2D array of size n x n, n being the array's length.
2. After that apply a 'for' loop from diagonal (d) initialized to 2 until it remains less than n. (As in diagonal-0 and diagonal-1, we need to fill zeroes so we can leave them as it is because by default the matrix will have zeroes at each position).
3. Then we run a nested for loop initialized with i = 0 until (i + d) remains less than n; to fill each cell of the dth diagonal.
4. Then define a variable j and initialize it with i + d.
5. Then set the dp[i][j] with the maximum value.
6. Now we need to use one more nested 'for' loop to explore variation corresponding to each k. Then inside the nested for loop, at dp[i], keep adding dp[j] * dp[i - 1 - j].
7. Then inside the nested for loop, calculate the current score of triangulation for kth variation and compare it with the dp[i][j]. If the calculated value is greater than update the dp[i][j] with the new score.
8. At last, return dp[0][n-1].
For more clarity of this part, watch the below part of the video.