Do you think IIT Guwahati certified course can help you in your career?
Introduction
In this article, we will solve the problem of finding the minimum score triangulation of polygon by three methods: recursion, memoization with recursion, and finally, we will discuss an iterative DP approach.
Let’s get started with the problem statement.
Problem Statement
You are given an N sided polygon. Every vertex of the polygon is assigned a value. The vertices are given in the form of an array of N integers in the clockwise direction.
You need to divide the polygon into N - 2 triangles. Each triangle has a triangle value. The triangle value is calculated by finding the product of its vertices.
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:
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.
Some of the ways of triangulating are shown below:
But we can reduce the score further. The most optimal triangulation to obtain a minimum score is:
One possible way to find the minimum score is to try all possible triangulations of the polygon and calculate the scores for each. Then, choose the minimum score among them.
To get all possible triangulations of a given polygon, we will follow the steps below:
For a triangle, fix an edge of the polygon as one side of the triangle. Now, to get the third vertex, run a loop from i+1 to j-1.
Calculate the score of the triangle [i,j,k] by multiplying vertex[i], vertex[j] and vertex[k].
After choosing this triangle, there are two parts of the polygon left to be triangulated. One polygon is on the left side of the triangle and the other on the right, as illustrated below:
Since we got two sub-polygons, then the total score of triangulation of the main polygon will be- minScore(P) = minScore(P1) + minScore(P2) + vertex[i]*vertex[j]*vertex[k]
To get the minimum score for polygon P, the scores of polygon P1 and P2 should also be minimised.
Thus, we got two subproblems to be solved, which implies we can use recursion.
Let’s see the implementation of the recursive approach in the next section.
C++ Implementation(Recursive)
/*C++ code to find minimum score triangulation of polygon using recursion*/ #include <bits/stdc++.h> usingnamespacestd;
intminimumTriangleScoreHelper(vector<int> &vertex, int i, int j) { // if triangle can't be formed if (j - i < 2) { return0; }
// initialize result as infinite int res = INT_MAX;
// loop over all vertices between i and j for (int k = i + 1; k < j; k++) { res = min(res, minimumTriangleScoreHelper(vertex, i, k) + minimumTriangleScoreHelper(vertex, k, j) + vertex[i] * vertex[k] * vertex[j]); } return res; }
intminimumTriangleScore(vector<int> &vertex, int n) { int ans = minimumTriangleScoreHelper(vertex, 0, n - 1); return ans; }
intmain() { int n = 5; // number of vertices of polygon vector<int> vertex = {2, 4, 2, 5, 1}; // values of the vertices cout << "Minimum score triangulation of the polygon is: " << minimumTriangleScore(vertex, n) << endl; }
Output
Minimum score triangulation of the polygon is: 26
Time Complexity
O(n ^ (n - 3)), where n is the number of sides in the polygon.
Since we are traversing through the complete array for (n-3) times (until we reach an array having only 3 sides), the overall time complexity will be O(n ^ (n - 3)).
In the recursive approach, we are solving many subproblems repetitively. So, to reduce the time complexity, we can store the results of every subproblem, and when its value is needed later, we can simply use its stored value rather than calculate it again. This is called memoization.
The approach remains the same except for the additional 2D DP array to store the results. Let’s see its implementation.
C++ Implementation
/*C++ code to find minimum score triangulation of polygon using recursion and memoization */
#include <bits/stdc++.h> usingnamespacestd;
intminimumTriangleScoreHelper(vector<vector<int>> &memo, vector<int> &vertex, int i, int j) { if (memo[i][j] == 0) { /* iterate over all the vertices between i and j */ for (int k = i + 1; k < j; k++) { int curr_score = vertex[i] * vertex[k] * vertex[j];
// Left sub polygon int left_polygon = minimumTriangleScoreHelper(memo, vertex, i, k);
// Right subpolygon int right_polygon = minimumTriangleScoreHelper(memo, vertex, k, j);
intminimumTriangleScore(vector<int> &vertex, int n) { // If array size is zero, then return 0. if (vertex.empty()) { return0; }
// Creating a 2D DP table to store the results vector<vector<int>> memo(n, vector<int>(n, 0));
return minimumTriangleScoreHelper(memo, vertex, 0, n - 1); }
intmain() { int n = 5; // number of vertices of polygon vector<int> vertex = {2, 4, 2, 5, 1}; // values of the vertices cout << "Minimum score triangulation of the polygon is: " << minimumTriangleScore(vertex, n) << endl; }
Output
Minimum score triangulation of the polygon is: 26
Time Complexity
O(n^3), There are (n^2) DP states from dp[0][0] to dp[n-1][n-1]. It takes linear time to calculate each dp[i][j] as we have to run a loop from k=i+1 to k=j-1.
So, total time complexity becomes -
= Number of dp states * (Time complexity to calculate the result for each state)
= (n^2) * O(n)
= O(n^3).
Space Complexity
O(n^2), Since we use a 2D vector to store our previous results, the overall space complexity is O(n^2).
Dynamic Programming Approach
In this method, we will calculate the results to all the smaller subproblems iteratively and then use these to get the values of larger subproblems which is essentially a bottom-up approach.
The implementation of this approach is quite simple and easy to understand.
C++ Implementation
/*C++ code to find minimum score triangulation of polygon using dynamic programming */
#include <bits/stdc++.h> usingnamespacestd;
intminimumTriangleScore(vector<int> &vertex, int n) { vector<vector<int>> dp(n, vector<int>(n)); /* each dp[i][j] denotes the minimum score to triangulate the polygon from vertex i to vertex j */ for (int j = 2; j < n; ++j) { for (int i = j - 2; i >= 0; --i) { dp[i][j] = INT_MAX; for (int k = i + 1; k < j; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + vertex[i] * vertex[j] * vertex[k]); } } return dp[0][n - 1]; }
intmain() { int n = 5; // number of vertices of polygon vector<int> vertex = {2, 4, 2, 5, 1}; // values of the vertices cout << "Minimum score triangulation of the polygon is: " << minimumTriangleScore(vertex, n) << endl; }
Output
Minimum score triangulation of the polygon is: 26
Time Complexity
O(n^3), as there are three nested loops.
Space Complexity
O(n^2), as we are using a 2D DP array of size n*n.
What is recursion? Recursion is a method of solving a problem in terms of similar but smaller subproblems. Learn more about recursion in detail here.
What is dynamic programming? Dynamic Programming or DP is just an optimization technique. It is a method for solving problems by breaking them down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. Do check out Roadmap For Beginners To Master Dynamic Programming
Key Takeaways
In this article, we learned how to solve the problem of finding the minimum score triangulation of polygon by three methods: recursion, memoization with recursion, and finally, the iterative DP approach. At first glance, it’s difficult to come up with a DP solution directly, but you will definitely be able to solve these types of problems with more practice.
Problems based on a similar concept that you must give a try -
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series onCoding Ninjas Studionow!
84+ registered