# Minimum Score Triangulation of Polygon Leetcode Solution

Difficulty Level Medium
algorithms coding Dynamic Programming Interview interviewprep LeetCode LeetCodeSolutionsViews 1066

## Problem statement

In the problem ” Minimum Score Triangulation of Polygon” we are given a value array where each element in the array represents the value of a N-sided polygon when labeled in a clockwise direction.

Our task is to triangulate the polygon into N-2 triangles. The score to triangulate a triangle is the product of the values at its three vertices.  The total score to triangulate a polygon is the sum of all scores of all the triangulation.

We have to find the minimum score of triangulation of a polygon.

### Example

`values = [1,3,1,4,1,5]`
`13`

Explanation:  We will get a minimum score for triangulation when we triangulate the polygon in this way:

1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13

## Approach for Minimum Score Triangulation of Polygon Leetcode Solution

Keeping in mind that we have to triangulate the polygon into N-2 triangles and the triangles Should not be overlapping. Every edge of the polygon can be a part of at most one triangle as overlapping is not allowed.

So every edge of the polygon can form a triangle with N-2 remaining vertices. Refer to the image below. When we cut a triangle from the polygon we are left with a new smaller polygon. This led us to the point that we can break a problem into smaller subproblems. So if we want a minimum score for a polygon with vertex from 0-6 then the new subproblem is the minimum score for a polygon with vertex from 0-3 and 3-6.

hence the recursive relation becomes:

minScore( pos1, pos2) = minScore(pos1,i,A) + minScore(i,pos2,A) + A[pos1]*A[pos2]*A[i]

To overcome the recomputation of the same subproblem again and again we will use a memorization table. This will be a n*n array where the value at i,j will store the minimum score triangulation of polygon with vertices from i to j.

### C++ code for Minimum Score Triangulation of Polygon

```#include <bits/stdc++.h>
using namespace std;
int memo;

int dp(int pos1,int pos2, vector<int>&A){
if(pos2-pos1<=1)return 0;

if(memo[pos1][pos2]!=-1)return memo[pos1][pos2];
int ans=INT_MAX;
for(int i=pos1+1;i<pos2;i++)
ans=min(ans, dp(pos1,i,A) + dp(i,pos2,A) + A[pos1]*A[pos2]*A[i] );
memo[pos1][pos2]=ans;
return ans;
}

int minScoreTriangulation(vector<int>& A) {
memset(memo,-1,sizeof(memo));
return dp(0,A.size()-1,A);
}
int main()
{
vector<int> arr = {1,3,1,4,1,5};
cout<<minScoreTriangulation(arr)<<endl;
return 0;
}```
`13`

### Java code for Minimum Score Triangulation of Polygon

```import java.util.Arrays;
public class Tutorialcup {
public static int minScoreTriangulation(int[] A) {
return dp(A, 0, A.length - 1, new Integer[A.length][A.length]);
}
public static int dp(int[] A, int pos1,int pos2, Integer[][] memo){
if(pos2-pos1<=1)return 0;

if(memo[pos1][pos2] != null)return memo[pos1][pos2];
int ans=Integer.MAX_VALUE;
for(int i=pos1+1;i<pos2;i++)
ans=Math.min(ans, dp(A,pos1,i,memo) + dp(A,i,pos2,memo) + A[pos1]*A[pos2]*A[i] );
memo[pos1][pos2]=ans;
return ans;
}
public static void main(String[] args) {
int [] arr = {1,3,1,4,1,5};
int ans= minScoreTriangulation(arr);
System.out.println(ans);
}
}```
`13`

## Complexity Analysis of Minimum Score Triangulation of Polygon Leetcode Solution

### Time complexity

The time complexity of the above code is O(n*n*n) because we are traversing the value array for 3 different i,j,k values that give a minimum score for triangulation of the polygon. Here n is the length of the value array.

### Space complexity

The space complexity of the above code is O(n*n) because using n*n extra space for memorization.

References

Translate »