给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5示例 2：
输入：n = 1
输出：1提示：
1 <= n <= 19
解法一：动态规划
状态表示
一般这类动态规划，找状态表示比较难，都是通过 “举例 + 抽象出相同的子问题” 来表示状态！
比如这里 n = 3 的情况：
我们分别让 1~n 的每个数依次插入二叉树，可以推断当确定了一个根节点之后，左右字数的节点个数就确定了！此时左右子树又会变成相同的子问题，因此我们可以定义状态表示为：dp[i] 表示当节点数量为 i 时，一共有多少颗 BST！
此时其实就可以将上面的情况划分一下：
难的是如何推导状态转移方程，因为它跟我们之前常见的状态转移方程不是很像。
状态转移方程
对于 dp[i]，表示此时有 i 个节点，那么此时对于所有不同的 BST 来说，我们可以按照以下规则来划分，分成不同的 i 类：
- 以
1元素为根节点的所有BST - 以
2元素为根节点的所有BST - ……
此时如果我们能求出每一个元素为根节点的所有 BST，然后将它们累加起来，不就是 dp[i] 了吗，对不对！
所以我们现在专门针对某个元素为根节点来研究一下会有多少 BST，假设此时以 j 为根节点：
- 对于
j根节点的左子树来说：- 此时左子树的节点编号为
[1, j - 1]，一共有j - 1个节点，根据状态表示，那就是dp[j - 1]。
- 此时左子树的节点编号为
- 对于
j根节点的右子树来说：- 此时右子树的节点编号为
[j + 1, i]，一共有i - j个节点，根据状态表示，就是dp[i - j]。
- 此时右子树的节点编号为
而又因为二叉搜索树的左右子树个数问题其实是一个排列问题，就可以得到 dp[j] = dp[j - 1] * dp[i - j]。
因此，我们只需要把不同节点为根节点的 BST 个数进行累加，就能得到 dp[i] 了！
初始化
因为我们会开辟虚拟行列，而 dp[0] 就相当于是没节点，其实这也属于一种二叉搜索树，所以初始化 dp[0] = 1 即可！
遍历顺序
因为需要用到前面的元素，所以要从左往右遍历！
返回值
根据状态表示，返回 dp[n] 即可！
class Solution {
public:
int numTrees(int n) {
// 创建dp表，dp[i]表示有i个节点时，一共有多少种BST
vector<int> dp(n + 1, 0);
// 初始化
dp[0] = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j) // 只需要遍历到i即可
dp[i] += dp[j - 1] * dp[i - j]; // 注意这里是累加，不是赋值！！！
return dp[n];
}
};💥解法二：卡特兰数
卡特兰数递推式如下所示：
事实上我们在方法一中推导出的方程是称为卡特兰数。
而我们其实可以通过上面的递推式，直接进行求解：
class Solution {
public:
int numTrees(int n) {
// 只需要一个变量即可！注意要用长整型，防止溢出
long long Cn = 1;
for(int i = 1; i < n; ++i)
Cn = ((4*i + 2) * Cn) /(i + 2);
return Cn;
}
};