The math explanation of this problem can be found at

https://www.quora.com/Given-n-how-many-structurally-unique-BSTs-binary-search-trees-that-store-values-1-to-n-are-there

I tried first to give a pure recursive solution but found TLE, then I introduced attribute "seen" to store the already calculated result to speed up. And it works well.

```
class Solution(object):
seen = {0:1, 1:1}
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
if n in Solution.seen:
return Solution.seen[n]
else:
result = 0
for i in range(1,n+1):
result += Solution.seen.get(i-1, self.numTrees(i - 1)) \
* Solution.seen.get(n-i,self.numTrees(n - i))
Solution.seen[n] = result
return result
```