Program for nth Catalan Number using Dynamic Programming

Program for nth Catalan Number using Recursion:

Program for nth Catalan Number using Binomial Coefficient:

We can observe that the above recursive implementation does a lot of repeated work. Since there are overlapping subproblems, we can use dynamic programming for this.

Step-by-step approach:

Create an array catalan[] for storing ith Catalan number.
Initialize, catalan[0] and catalan[1] = 1
Loop through i = 2 to the given Catalan number n.
- Loop through j = 0 to j < i and Keep adding value of catalan[j] * catalan[i – j – 1] into catalan[i].
Finally, return catalan[n]

Follow the steps below to implement the above approach:

C++

#include <iostream>
using namespace std;
 
// A dynamic programming based function to find nth
// Catalan number
unsigned long int catalanDP(unsigned int n)
{
    // Table to store results of subproblems
    unsigned long int catalan[n + 1];
 
    // Initialize first two values in table
    catalan[0] = catalan[1] = 1;
 
    // Fill entries in catalan[] using recursive formula
    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 last entry
    return catalan[n];
}
 
// Driver code
int main()
{
    for (int i = 0; i < 10; i++)
        cout << catalanDP(i) << " ";
    return 0;
}

Java

import java.io.*;
class GFG {
 
    // A dynamic programming based function to find nth
    // Catalan number
    static int catalanDP(int n)
    {
        // Table to store results of subproblems
        int catalan[] = new int[n + 2];
 
        // Initialize first two values in table
        catalan[0] = 1;
        catalan[1] = 1;
 
        // Fill entries in catalan[]
        // using recursive formula
        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 last entry
        return catalan[n];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        for (int i = 0; i < 10; i++) {
            System.out.print(catalanDP(i) + " ");
        }
    }
}
// This code contributed by Rajput-Ji

Python3

# A dynamic programming based function to find nth
# Catalan number
 
 
def catalan(n):
    if (n == 0 or n == 1):
        return 1
 
    # Table to store results of subproblems
    catalan = [0]*(n+1)
 
    # Initialize first two values in table
    catalan[0] = 1
    catalan[1] = 1
 
    # Fill entries in catalan[]
    # using recursive formula
    for i in range(2, n + 1):
        for j in range(i):
            catalan[i] += catalan[j] * catalan[i-j-1]
 
    # Return last entry
    return catalan[n]
 
 
# Driver code
for i in range(10):
    print(catalan(i), end=" ")
# This code is contributed by Ediga_manisha

C#

using System;
 
class GFG {
 
    // A dynamic programming based
    // function to find nth
    // Catalan number
    static uint catalanDP(uint n)
    {
        // Table to store results of subproblems
        uint[] catalan = new uint[n + 2];
 
        // Initialize first two values in table
        catalan[0] = catalan[1] = 1;
 
        // Fill entries in catalan[]
        // using recursive formula
        for (uint i = 2; i <= n; i++) {
            catalan[i] = 0;
            for (uint j = 0; j < i; j++)
                catalan[i]
                    += catalan[j] * catalan[i - j - 1];
        }
 
        // Return last entry
        return catalan[n];
    }
 
    // Driver code
    static void Main()
    {
        for (uint i = 0; i < 10; i++)
            Console.Write(catalanDP(i) + " ");
    }
}
 
// This code is contributed by Chandan_jnu

Javascript

<script>
// Javascript program for nth Catalan Number
 
// A dynamic programming based function 
// to find nth Catalan number
function catalanDP(n)
{
     
    // Table to store results 
    // of subproblems
    let catalan= [];
 
    // Initialize first two 
    // values in table
    catalan[0] = catalan[1] = 1;
 
    // Fill entries in catalan[] 
    // using recursive formula
    for (let i = 2; i <= n; i++)
    {
        catalan[i] = 0;
        for (let j = 0; j < i; j++)
            catalan[i] += catalan[j] * 
                   catalan[i - j - 1];
    }
 
    // Return last entry
    return catalan[n];
}
 
    // Driver Code
    for (let i = 0; i < 10; i++)
        document.write(catalanDP(i) + " ");
 
// This code is contributed _saurabh_jaiswal
</script>

PHP

<?php
// PHP program for nth Catalan Number
 
// A dynamic programming based function 
// to find nth Catalan number
function catalanDP( $n)
{
     
    // Table to store results 
    // of subproblems
    $catalan= array();
 
    // Initialize first two 
    // values in table
    $catalan[0] = $catalan[1] = 1;
 
    // Fill entries in catalan[] 
    // using recursive formula
    for ($i = 2; $i <= $n; $i++)
    {
        $catalan[$i] = 0;
        for ( $j = 0; $j < $i; $j++)
            $catalan[$i] += $catalan[$j] * 
                   $catalan[$i - $j - 1];
    }
 
    // Return last entry
    return $catalan[$n];
}
 
    // Driver Code
    for ($i = 0; $i < 10; $i++)
        echo catalanDP($i) , " ";
 
// This code is contributed anuj_67.
?>

Output

1 1 2 5 14 42 132 429 1430 4862

Time Complexity: O(n²)
Auxiliary Space: O(n)

Program for nth Catalan Number

Catalan numbers are defined as a mathematical sequence that consists of positive integers, which can be used to find the number of possibilities of various combinations.

The nth term in the sequence denoted C_n, is found in the following formula:

The first few Catalan numbers for n = 0, 1, 2, 3, … are : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

Catalan numbers occur in many interesting counting problems like the following.

Count the number of expressions containing n pairs of parentheses that are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
Count the number of possible Binary Search Trees with n keys (See this)
Count the number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.
Given a number n, return the number of ways you can draw n chords in a circle with 2 x n points such that no 2 chords intersect.

See this for more applications.

Examples:

Input: n = 6
Output: 132

Input: n = 8
Output: 1430

Tags:

#Amazon #catalan #series #DSA #Dynamic Programming #Mathematical #Amazon #Dynamic Programming #Mathematical #series