文章目录
问题描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 19
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
法I：动态规划（二维）
memo是二维的，我们用memo[i][j]来记录从i到j可以形成的子树数目。
其实有一点对理解题意很重要。所有结点是从1到n，我们确定一个根结点为k，那么左子树的所有结点就是[1,k-1]，右子树的所有结点是[k+1,n]。也就是一个根结点的一个子树的所有可用结点是连续的，问题规模缩小时也同样成立。因此我们就用[i,j]来记录这棵子树的可用结点为从i到j的所有结点，也用memo[i][j]来记录这样的子树的数目。计算时，需要遍历从i到j分别为这棵子树的根结点，进一步用更小的子问题结果来计算这个大问题的解。
//动态规划
class Solution {
public:
int numTrees(int n) {
//建立备忘录memo并赋初值
vector<vector<int>> memo(n, vector<int>(n));
for (int i = 0; i < n; i++) {
memo[i][i] = 1;
}
//开始动态规划
for (int m = 1; m < n; m++) {
for (int i = 0; i < n - m; i++) {
int j = i + m;
int k = i;
memo[i][j] = memo[k + 1][j];
for (k = i + 1; k < j; k++) {
memo[i][j] += memo[i][k - 1] * memo[k + 1][j];
}
k = j;
memo[i][j] += memo[i][k - 1];
}
}
return memo[0][n - 1];
}
};
法II：动态规划（一维）
同样是动态规划，我们来思考一下有没有更小的memo来记录结果。根据我们对题意的理解，由于一棵子树的所有可用结点一定是连续的，我们可以推断出，其实这棵子树的所有可能情况的数目只与其可用结点的数目有关，这样我们好像就可以直接把memo降为一维了诶！
那我们就来上一下代码吧：
//动态规划（一维）
class Solution {
public:
int numTrees(int n) {
//建立memo并赋初值
vector<int> memo(n + 1, 0);
memo[0] = 1;
memo[1] = 1;
if (n >= 2) {
for (int i = 2; i <= n; i++) {//i代表一棵子树所有可用结点的数目
for (int j = 0; j < i; j++) {//j代表这棵子树的左子树的可用结点数目
memo[i] += memo[j] * memo[i - j - 1];
}
}
}
return memo[n];
}
};
法III：数学方法
我觉得看看就行了
class Solution {
public:
int numTrees(int n) {
long long C = 1;
for (int i = 0; i < n; ++i) {
C = C * 2 * (2 * i + 1) / (i + 2);
}
return (int)C;
}
};