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 –

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

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:

Get Free Certificate of Merit in Data Structure I 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

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Practice Computer Science MCQs
Apply for Information Technology Internship
Buy Computer Science Books
Apply for Computer Science Internship

Recommended Articles: