O(n2) where n is the number of sides of the polygon that we have to triangulate.

O(n)

1. The number of ways in which we can triangulate a polygon of sides N is the (N-2)th Catalan number. So, we just have to find the (N-2)th Catalan Number. The algorithm to find Nth Catalan number is given below
2. Create a dp array of size n+1 where n is the input Catalan number.
3. Fill dp[0]=1 and dp[1]=1 and then start the outer loop from i=2 to i=n.
4. Start the inner loop from j=0 to less than I i.e. j=0 to j < i.
5. Use the formula dp[i] += dp[j] x dp[i-j-1] inside the inner loop to fill the array with the Catalan numbers.
6. Print dp[n] as the answer.

The "what" of the problem is simple. We will generate (N-2)th Catalan Number and this will be the number of ways in which we can triangulate a polygon of N sides.

Let us now try to find the "why" of the problem i.e. why the (N-2)th Catalan Number gives us our answer. Let us take different input values and try to analyze the number of ways in which we can triangulate a polygon having N sides.

When the input value of N is less than 3, our answer will be 0. This is because we cannot triangulate a shape with less than three sides.

The minimum sized polygon is a triangle and we need three sides for it. So, if we are given less than three sides, the shape is not even a polygon and we cannot triangulate it.

You might think that we can triangulate a shape of 2 sides as shown below

We cannot triangulate a figure which is not a polygon as the question is about triangulating a polygon only. Hence this triangulation is not valid and the number of ways of triangulating an N-sided figure when N < 3 is 0.

When N=3, the given polygon is a triangle itself. So, there is only one way to triangulate it, do not do anything with the polygon. You might be thinking that we can triangulate this polygon also in the way as shown:

We can't do this because of the reason mentioned in the diagram only.

Till now we have discussed what you can call the base cases i.e. the inputs for which we do not need to calculate any answer. Now, before we move forward, we want to change our method of thinking a little bit. See, when we talk about a 3-sided or a 4-sided or a 5-sided polygon and so on, we will notice that the number of vertices and edges of these shapes are equal.

For instance, a triangle has 3 vertices and three edges and a quadrilateral has 4 vertices and 4 edges, and so on. So, first of all, we will now replace the sides with vertices i.e. we will now stop thinking of the solution keeping the sides in our mind. Now, we will talk about the N-vertexed polygons rather than N-sided polygons.

Also, we will assume that we have one way to create a triangle if the number of vertices given to us is 2. If the number of vertices is 2, we have only one straight line. So, we are assuming that there is a way to triangulate this figure where the third point lies on the line itself. We can call this a triangle of size 0.

Note: Please note that this is just an assumption to make our work easier for further cases. We know that this does not make much sense now to you, but it will when we move forward. Also, whenever we get an input N < 3, we will print 0 only. This assumption is being done so that we can derive the answer for the next upcoming cases.

When n=4: When n=4, we have 2 ways to triangulate it as shown in the figure below:

Let us verify also that there are only 2 ways to triangulate a 4-vertex polygon. So, we will first join vertex 1 and 2 and make a triangle T1(1,3,4).

Towards the left of the triangle T1, we can see that there are 2 points on the base and we can see 3 points on its right.

So, the number of ways in which we can triangulate the quadrilateral if we join the points 1 and 4 is the number of ways of triangulation of 2-vertex polygon multiplied by the number of ways of triangulation of 3-vertex polygon. We know that a 3vertex polygon can be triangulated in 1 way and a 2-vertex polygon is assumed to be triangulated in 1 way too. So, we get the answer 1 x 1=1 i.e. the only way shown already in the image above.

The same will be the case for the second quadrilateral and the total answer will be 1+1=2.

We have calculated the triangulation of a 4-vertex polygon as shown in the image below:

Also, triangulation of 2-vertex polygon and triangulation of 3-vertex polygon is 1 and 1. If we look at the Calculation of the 2nd Catalan number it looks like this:

This looks the same. So, we can say that the number of ways of triangulation of a 2-vertex polygon is the same as the 0th Catalan number and the number of ways of triangulation of a 3-vertex polygon is the same as the 1st Catalan number and so on.

So, the number of ways of triangulation of an N-vertex (N-sided) polygon (when N>3) is the (N-2)th Catalan number

Let us try this on a pentagon too so that we can be sure of this conclusion and also understand the concept in more detail and depth.

When n=5: Firstly, we can have three figures to start with as shown in the image below:

Let us start with the first figure. We can see that it has 2 points on the left and 4 points to the right. So, the number of ways in which it can be triangulated is as shown below:

Now, let us calculate the number of ways of triangulation of the second figure in above image.

The third figure in the same figure is similar to the first figure.

So, when N=5, the answer comes out to be 5.

So, the number of ways in which we can triangulate a polygon of sides 5 is the 3rd Catalan number.

We hope that you have now understood how we concluded that the number of ways of triangulation of an N-sided polygon when N>2 is the (N-2)th Catalan number.

We recommend you refer to the solution video to understand the above-explained part of the article and also see the derivation of this proof for a hexagon. This hexagon example is quite long so we couldn't cover it here but it is covered in-depth in the video and it will build your insight into this concept up to some unimaginable level.

Now that we have covered everything, let us write the code for this problem.