题目描述

给定一个整数 n，求以 1… n 为节点组成的不同的二叉搜索树有多少种？

例如，给出 n = 3，则有 5 种不同形态的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

最优解法——DP（AC）

见https://blog.csdn.net/sunnyyoona/article/details/42177001
复杂度O(n2)
结果：Beat50.37%

class Solution:
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0] * (n + 1)
        
        
        dp[0] = 1
        if(n != 0):
            dp[1] = 1

        for i in range(2,n + 1):
            for k in range(1,i + 1):
                dp[i] += dp[i - k] * dp[k - 1]
        print(dp)
        return dp[n]