题目

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]