给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 19 解题思路
这题的解题思路是 DP。dp[n] 代表 1-n个数能组成多少个不同的二叉排序树，F(i,n) 代表以i 为根节点，1-n个数组成的二叉排序树的不同的个数。
由于题意，我们可以得到这个等式：
d
p
[
n
]
=
F
(
1
,
n
)
+
F
(
2
,
n
)
+
F
(
3
,
n
)
+
…
…
+
F
(
n
,
n
)
dp[n] = F(1,n) + F(2,n) + F(3,n) + …… + F(n,n)
dp[n]=F(1,n)+F(2,n)+F(3,n)+……+F(n,n)
初始值 dp[0] = 1，dp[1] = 1。
分析 dp 和 F(i,n) 的关系又可以得到下面这个等式
F
(
i
,
n
)
=
d
p
[
i
−
1
]
∗
d
p
[
n
−
i
]
F(i,n) = dp[i-1] * dp[n-i]
F(i,n)=dp[i−1]∗dp[n−i]
举例，[1,2,3,4,…, i ,…,n-1,n]，以 i为 根节点，那么左半边 [1,2,3,……,i-1]和 右半边[i+1,i+2,……,n-1,n]分别能组成二叉排序树的不同个数相乘，即为以 i 为根节点，1-n 个数组成的二叉排序树的不同的个数，也即 F(i,n)。
class Solution {
public:
int numTrees(int n) {
vector dp(n + 1);
dp[0] = 1, dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
};
