题目如下：

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3Output: 5Explanation:Given n = 3, there are a total of 5 unique BST's:   1         3     3      2      1    \       /     /      / \      \     3     2     1      1   3      2    /     /       \                 \   2     1         2                 3

解题思路：一开始我觉得递归就行了，根节点可以填入的数为[1,2,3....n]，如果选择该根节点值为2，那么其左边子树可以选择的就是[1]，而右边子树可以选择的就是[3...n]，所以根节点为2可以构成的树的总量就是左边子树的种数*右边子树的总数，依次累计根节点填入1~n的总数即可。

代码如下：

class Solution(object):    dic = {}    def recursive(self,nl):        if (nl[0],nl[-1]) in self.dic:            return self.dic[(nl[0],nl[-1])]        if len(nl) == 1:            self.dic[(nl[0], nl[-1])] = 1            return 1        count = 0        for i in range(len(nl)):            l1 = nl[:i] if i > 0 else []            l2 = nl[i+1:]            if len(l1) + len(l2) == 0:                count += 0            elif len(l1) == 0:                count += self.recursive(l2)            elif len(l2) == 0:                count += self.recursive(l1)            else:                count += (self.recursive(l1) * self.recursive(l2) )        self.dic[(nl[0], nl[-1])] = count        return count    def numTrees(self, n):        """        :type n: int        :rtype: int        """        self.dic = {}        return self.recursive(range(1,n+1))