Challenge
Your task is to print the Nth catalan number.
catalan(5) = 42
Solution
Bottom up
def catalan(n):
res = [0 for i in range(n+1)]
res[0] = 1
s = 0
for i in range(1, n+1):
for j in range(0, i):
res[i] += res[j] * res[i-j-1]
return res[n]
Time Complexity: O(n^2)
Top Down
def catalan(n):
if n == 0 or n ==1:
return 1
s = 0
for i in range(n):
s += catalan(i) * catalan(n-1-i)
return s
Time Complexity: O(n!)
Application
- Find the number of unique BST.