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:

Free 30-Day Python Certification Bootcamp is Live. Join Now!

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.

```
#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;
```
```
}
```

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.

« Prev - Newspaper Headline Problem using Dynamic Programming

» Next - Alice Kindergarten Candies Problem using Dynamic Programming

Related Posts:

Check Computer Science Books
Practice Design & Analysis of Algorithms MCQ
Practice Programming MCQs
Apply for Computer Science Internship
Check Data Structure Books

Recommended Articles: