Nth catalan number

Recursion :

def findCatalan(n):
    def recur(n):
        if n == 0 or n == 1:
            return 1
        res = 0
        for i in range(n):
            res += recur(i) * recur(n-i-1)
        return res
    return recur(n)

Top down :

def findCatalan(n): 
    def top_down(n,dp):
        if dp[n] != -1:
            return dp[n]
        res = 0
        for i in range(n):
            res += top_down(i,dp) * top_down(n-i-1,dp)
        dp[n] = res
        return dp[n]
    
    dp = [-1] * (n+1)
    dp[0] = 1
    dp[1] = 1
    return top_down(n,dp)

Bottom Up:

def findCatalan(n): 
    def bottom_up(n,dp):
        for i in range(2,n+1):
            for j in range(i):
                dp[i]  += dp[j] * dp[i-j-1]
    
    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 1
    bottom_up(n,dp) # Calling function
    return dp[n]

Source: practice.geeksforgeeks.org

Similar codes

0 vote275 views1 answer
How to keep old content when using write in python
Python
1 vote255 views1 answer
Make python look good
Python
1 vote239 views1 answer
Pip install django celery results
Python
0 vote261 views1 answer
Webdriver antibot
Python
1 vote286 views5 answers
How to install django in virtual environment in ubuntu
Python Django
1 vote210 views1 answer
Python pandas row standard deviation
Python
2 votes233 views1 answer
Discord.py get user id from message
Python
3 votes249 views4 answers
Create a new dataframe from existing dataframe pandas
Python
0 vote280 views1 answer
Date format django template filter
Python
0 vote263 views1 answer
The Python 2 bindings for rpm are needed for this module. If you require Python 3 support use the `dnf` Ansible module instead.. The Python 2 yum module is needed for this module. If you require Python 3 support use the `dnf` Ansible module instead.
Python