```
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return 2
num = [0]*(n+1)
num[0:3] = [0,1,2]
for i in range(3,n+1):
for j in range(2,i):
num[i] += num[j-1]*num[i-j]
num[i] += num[i-1]*2
return num[n]
```

Suppose the number of solution with n is f(n). Then for n, the possible cases for root are 1, 2,..., n. For any root, i, f(i) = f(i-1) * f(n-i) since there are (i-1) number in the left subtree, and (n-i) number in the right subtree. Note that if i-1== 0 (or n-i==0), f(i)=f(n-i) (or f(i-1)).

Another thing to mention is DON'T use recursive calls in such problems. Although it will give you correct answer, it will exceed time limit.