96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

Python 解答：
1.动态规划

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

2.数学，卡特兰数

class Solution:
    def numTrees(self, n: int) -> int:
        c0 = 1
        for i in range(n):
            c1 = c0*2*(2*i+1)//(i+2)
            c0 = c1
        return c1