Apparently, any BST in size of n will have n partitions, for example [0,...i ], i+1, [i+2,...n]. where i+1 represent the root.

Then we can simply reduce the question. Here's the code

**DP**

```
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0: return 0
dp = [0 if _ > 1 else 1 for _ in xrange(n+1)]
for i in xrange(2, n+1):
for j in xrange(0, i):
dp[i] += dp[j] * dp[i-1-j]
return dp[-1]
# 79 ms
```