Dynamic Programming: Get the nth catalan number

Problem Statement:

You are given an integer “n”, you need to get the “nth” catalan number.

What is a Catalan Number?

A catalan number are a sequence of natural number that occur in a specific sequence.

So the catalan number are:

C(0) = 1
C(1) = 1
C(2) = 2
C(3) = 5
C(4) = 14

So how did we arrive at the numbers?

C(0) = C(1) = 1

C(2) = C0C1 + C1C0
     = 1*1 + 1*1 = 2

C(3) = C0C2 + C1C1 + C2C0
     = 2 + 1 + 2 = 5

C(4) = C0C3 + C1C2 + C2C1 + C3C0
     = 5 + 2 + 2 + 5 = 14

So for C(n) = C0Cn-1 + C1Cn-2 + ... + CiCn-i-1 + ... + Cn-1C0

Solution

Method 1: Recursive Approach:

We can get the solution by using below formula:

Result += catalan(i) * catalan(n-i-1)

Method 2: DP

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <queue>

using namespace std;


long int get_n_catalan_using_recursion(unsigned int n)
{
    if (n <= 1)
        return 1;
 
    unsigned long int result = 0;
    for (int i = 0; i < n; i++)
        result += get_n_catalan_using_recursion(i) 
            * get_n_catalan_using_recursion(n - i - 1);
 
    return result;
}


long int get_n_catalan_using_DP(unsigned int n)
{
   long int catalan[n + 1];
 
    catalan[0] = catalan[1] = 1;
 
    for (int i = 2; i <= n; i++) 
    {
        catalan[i] = 0;
        for (int j = 0; j < i; j++)
            catalan[i] += catalan[j] * catalan[i - j - 1];
    }
 
    return catalan[n];
}
 
int main()
{

        cout <<"The 10th catalan number using recursion are = " << get_n_catalan_using_recursion(10) << endl;
        cout <<"The 10th catalan number using DP are = " << get_n_catalan_using_DP(10) << endl;
    return 0;
}

Output:

The 10th catalan number using recursion are = 16796
The 10th catalan number using DP are = 16796