Catalan Number

Dynamic programming 

Catalan Number are a sequence of a natural number that occur in many problem like following:

1. Count the number of expression containing n pair of parenthesis.

2. Count the number of possible binary search tree with n keys. 

Example n=3 , than formula is  C_0=1 \ and \ C_n_+_1=\sum_{i=0}^{n}C_iC_n_-_i \ for \ n\geq 0;

than C2+1=C3=C0*C2+C1*C1+C2*C0

= C3=5

Solution:

n=int(input("Enter the number"))

catalan=[0 for i in range(n+1)]

catalan[0]=1

catalan[1]=1

res=[]

for i in range(2,n): 

    catalan[i]=0

    for j in range(i):

        catalan[i]+=catalan[j]*catalan[i-j-1]

print(catalan)