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]