1、题目描述：

2、题解：

方法1：动态规划：
动态规划问题，弄清楚三点：

1、重复子问题；
2、最优子结构；
3、无后效性。

动态规划：

1、状态定义；
2、状态转移方程；
3、初始化；base case
4、输出；
5、思考状态压缩。

可以用递归去求，但是会存在重叠子问题，加个备忘录可以解决重复问题。
状态定义：
dp[i] 为第i个数为根结点的BST的数量。以k为根结点的BST种类数=左子树BST种类数+右子树BST种类数
状态转移方程：

dp[i] = dp[0]*d[i-1] + dp[1]*dp[i-2] + ... +dp[i-1]*dp[0]

base case:
dp[0] = 1,解释：当没有数字时，空树
dp[1] = 1，当一个数字是，只能形成一种BST：单个结点
python代码如下：

class Solution:
    def numTrees(self, n: int) -> int:
        #动态规划
        dp = [0] * (n + 1)
        dp[0],dp[1] = 1,1
        for i in range(2,n+1):
            for j in range(i):
                dp[i] += dp[j] * dp[i-j-1]
        return dp[n]

方法2：递归
未优化的，python会超时

class Solution:
    def numTrees(self, n: int) -> int:
        #递归 超时
        if n == 0 or n == 1:return 1
        num = 0
        for i in range(n):
            num += self.numTrees(i) * self.numTrees(n-i-1)
        return num

优化：记忆化递归

class Solution:
    def numTrees(self, n: int) -> int:
        #递归 优化 记忆化递归
        memo = [0] * (n + 1)
        def recur(n):
            if n == 0 or n == 1:return 1
            if memo[n] > 0:return memo[n]
            for i in range(n):
                memo[n] += recur(i) * recur(n-i-1)
            return memo[n]
        return recur(n)

方法3：卡特兰公式

class Solution:
    def numTrees(self, n: int) -> int:
        #卡特兰公式
        G = [0]*(n+1)
        G[0], G[1] = 1, 1

        for i in range(2, n+1):
            for j in range(1, i+1):
                G[i] += G[j-1] * G[i-j]

        return G[n]

方法4：数学法
卡特兰数：

class Solution:
    def numTrees(self, n: int) -> int:
        #卡特兰数
        res = 1
        for i in range(n):
            res = res * 2(2 * i + 1)/(i + 2)
        return int(res)

3、复杂度分析：

方法1：
时间复杂度：O(N^2)
空间复杂度：O(N)
方法2：
时间复杂度：O(N)
空间复杂度：O(N)
方法3：
时间复杂度：O(N^2)
空间复杂度：O(N)
方法4
时间复杂度：O(N)
空间复杂度：O(1)