dp[2] =  dp[0] * dp[1]　　　(1为根的情况)

　　　　+ dp[1] * dp[0]　　  (2为根的情况)

同理可写出 n = 3 的计算方法：

dp[3] =  dp[0] * dp[2]　　　(1为根的情况)

　　　　+ dp[1] * dp[1]　　  (2为根的情况)

 　　　  + dp[2] * dp[0]　　  (3为根的情况)
catalan numbers

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        d=[0 for i in xrange(n+1)]
        d[0],d[1]=1,1
        
        for i in xrange(2,n+1):
            for j in xrange(i):
                d[i]+=d[j]*d[i-1-j]
        return d[n]