This is a C++ Program that Solves Forming Triangles Problem – Catalan Numbers using Dynamic Programming technique.

In how many ways a plane convex polygon of n sides can be divided into triangles by diagonals?

This problem can be solved using catalan numbers. Catalan numbers forms a sequence of natural numbers based on a recursive formula(like fibonacci). Catalan numbers are used in various counting problems, this being one of them.

Let C[n]=nth catalan number

Total number of ways in which a convex polygon of n sides can be divided into triangles by diagonals = C[n-2]

Time Complexity of this solution is O(n^2).

Case-1:

If n=3, Expected result=1, the triangle itself

Case-2:

If n=4, Expected result=2, a quadrilateral can be divided into triangle in two ways (using one diagonal every time)

Case-3:

If n=5, Expected result=5

Here is source code of the C++ Program to Solve Forming Triangles Problem – Catalan Numbers. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`#include<iostream>`

using namespace std;

int catalan_polygon(int n)

`{`

`//we are given a convex polygon of n sides`

`//we have to find out in how many ways a plane convex polygon of n sides can be divided into triangles by diagonals`

`//result will be equal to (n-2)th catalan number ie, c[n-2]`

int c[n-1];

`//c[i]=total number of ways in which a plane convex polygon of (i+2) sides can be divided into triangles by diagonals`

`//initialize`

c[0]=1;

c[1]=1;

c[2]=2;

int i,j;

`//now, using bottom up DP, we will implement the recursive formula of catalan number to find the required value`

for(i=3;i<=(n-2);i++)

`{`

c[i]=0;

for(j=0;j<i;j++)

`{`

c[i]+=c[j] * c[(i-1)-j];

`}`

`}`

return c[n-2];

`}`

int main()

`{`

int n;

cout<<"Enter the number of sides in the convex polygon(>=3)"<<endl;

cin>>n;

cout<<"Total number of ways in which a convex polygon of "<<n<<" sides can be divided into triangles by diagonals is "<<endl;

cout<<catalan_polygon(n);

cout<<endl;

return 0;

`}`

In the main function, we ask the user to input the number of sides in the polygon. We pass this value to the function catalan_polygon as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Case-1: $ g++ catalan_polygon.cpp $ ./a.out Enter the number of sides in the convex polygon(>=3) 5 Total number of ways in which a convex polygon of 5 sides can be divided into triangles by diagonals is 5

**Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.**

To practice all Dynamic Programming Problems, __here is complete set of 100+ Problems and Solutions__.