Triangle Problem using Dynamic Programming

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

Problem Description

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

Problem Solution

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]

Recurrence relation –

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

Expected Input and Output

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```
Program/Source Code

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.

1. `#include<iostream>`
2. `using namespace std;`
3. ` `
4. `int catalan_polygon(int n)`
5. `{`
6. `    //we are given a convex polygon of n sides`
7. `    //we have to find out in how many ways a plane convex polygon of n sides can be divided into triangles by diagonals`
8. `    //result will be equal to (n-2)th catalan number ie, c[n-2]`
9. `    int c[n-1];`
10. ` `
11. `    //c[i]=total number of ways in which a plane convex polygon of (i+2) sides can be divided into triangles by diagonals`
12. ` `
13. `    //initialize`
14. `    c[0]=1;`
15. `    c[1]=1;`
16. `    c[2]=2;`
17. ` `
18. `    int i,j;`
19. ` `
20. `    //now, using bottom up DP, we will implement the recursive formula of catalan number to find the required value`
21. `    for(i=3;i<=(n-2);i++)`
22. `    {`
23. `        c[i]=0;`
24. ` `
25. `        for(j=0;j<i;j++)`
26. `        {`
27. `            c[i]+=c[j] * c[(i-1)-j];`
28. `        }`
29. `    }`
30. ` `
31. `    return c[n-2];`
32. `}`
33. ` `
34. `int main()`
35. `{`
36. `    int n;`
37. ` `
38. `    cout<<"Enter the number of sides in the convex polygon(>=3)"<<endl;`
39. `    cin>>n;`
40. ` `
41. `    cout<<"Total number of ways in which a convex polygon of "<<n<<" sides can be divided into triangles by diagonals is "<<endl; `
42. `    cout<<catalan_polygon(n);`
43. ` `
44. `    cout<<endl;`
45. `    return 0;`
46. `}`
Program Explanation

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.

Runtime Test Cases
```
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.