Unique Binary Search Trees

此题需要用到一个类似排列组合的规律来解题，我们可以把n想象成从1-n的n个结点一字排开，任何一个点作为BST的根节点时都只能选择自己左侧的结点作为左子树的构型，右边也一样，而以其中每一个点作为根节点的不同构型的BST的总数目就是最后的dp[n]，也就是说在计算dp[i]时我们必须枚举i之前的所有x和i - x - 1的组合来求解

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [1, 1, 2]

        for i in xrange(3, n + 1):
            dp.append(0)
            for j in xrange(1, i + 1):
                dp[i] += (dp[j - 1] * dp[i - j])

        return dp[n]