题目
1~n共n个数能组成几个不同的二叉查找树BST
例如：
n=3时，可以组成以下五个BST
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
分析
想明白了其实特别简单。假如结果为f(n)。每一个节点i都可以做根，然后把剩余的节点分成两部分[1, i-1] 和 [i+1, n]，分别构成f(i-1)个与f(n-i)个左右子树，每一种左子树都与一种右子树搭配构成一个完整的树，共有f(i-1)*f(n-i)种组合。把每一个节点i做树根的结果加起来，即为所求。
代码
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
nums = [1] + [0] * n
for i in range(1, n+1):
for r in range(i):
nums[i] += nums[r] * nums[i-r-1]
return nums[n]
