题目
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5示例 2：
输入：n = 1
输出：1提示：
1 <= n <= 19
解答
- 动态规划
解题思路： 这个问题可以用动态规划来解决。我们创建一个数组 dp，其中 dp[i] 表示以 i 个节点构建的二叉搜索树的数量。我们可以观察到，对于每个 i，我们可以将每个节点依次作为根节点，将问题划分为子问题。例如，以节点 j 作为根节点，它的左子树将有 j - 1 个节点，右子树将有 i - j 个节点。所以，以节点 j 作为根节点的二叉搜索树数量为 dp[j - 1] * dp[i - j]。我们将所有以不同节点作为根节点的情况累加起来，就得到了 dp[i] 的值。
在循环计算 dp 数组时，外层循环遍历节点数量 i，内层循环遍历以不同节点为根节点的情况 j。最终，dp[n] 就是我们所求的以 n 个节点构建的不同二叉搜索树的数量。
class Solution {
public:
int numTrees(int n) {
// 创建一个数组来存储以1到n为节点的二叉搜索树的数量
vector<int> dp(n + 1, 0);
// 空树也算一种情况，初始化dp[0]为1
dp[0] = 1;
// 外层循环遍历节点数量
for (int i = 1; i <= n; ++i) {
// 内层循环遍历以不同节点为根节点的情况
for (int j = 1; j <= i; ++j) {
// 左子树的节点数量为j-1，右子树的节点数量为i-j
// 以第j个节点为根节点的BST数量等于左子树数量乘以右子树数量
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
};