题目描述如下图：计算不同的二叉搜索树个数，如果有小伙伴对二叉搜索树不太清楚，建议去了解一下二叉搜索树是个什么东东，详细见如下博客：https://blog.csdn.net/qq_41836269/article/details/90402989
如果有问题，欢迎小伙伴指出哈。
分析：
思路：1~n中的每一个数字都可以作为树的根节点，如果能求出以1~n中每一个数字为根节点的不同二叉搜索树个数，求和即为所有的树的个数。那么以1~n中每一个数字为根节点的不同二叉搜索树个数又该怎么求呢？
a. 假设： f[i] : 表示以i为根节点的不同搜索二叉树的个数，则有如下结论： f[i] = i的左子树的个数 * i的右子树的个数（这里小伙伴们可以思考一下，其实就是一个组合问题，应该很好想到） i的左子树由1~(i-1)这i-1个数字组成的 i的右子树由(i+1) ~ n这n-i个数字组成的
b . 假设： G[n] : 表示有n个不同数字组成的二叉搜索树的个数 G[i-1] : 表示1~(i-1)组成的树的个数(i-1)个数字组成 G[n-i] ：表示(i+1)~n组成的树的个数(n-i)个数字组成
根据a,b我们可以得到：f[i] = G[i-1] * G[n-i]
下面分别介绍三种做题方法：
1.暴力搜索法，根据上面结论，我们可以给出暴力法的代码，算法时间复杂度为O(n!)
class Solution { public: int numTrees(int n) { return dfs(n); } int dfs(int n) { int ans = 0; if(n == 0 || n == 1) return 1; //这里的n == 0时返回1，是因为下面是相乘，如果返回0，就会强制得到0 for(int i = 1; i <= n; i++) { ans += dfs(i-1) * dfs(n-i); } return ans; } };以上的暴力法比动态规划方法容易想到，在做笔试的时候我们是第一时间能想到的，但是会超时，下面思考这种暴力法该如何优化，才能不超时呢？
我们在观察的时候，发现ans += dfs(i-1) * dfs(n-i),两次递归dfs(i-1)和dfs(n-i),当i~n变化时，会存在重复求解，因此可以从这里优化。观察发现，如果我们可以记录下(1~n)每一种情况的二叉搜索树个数，我们就可以避免重复求解。因此我们可以定义一个状态数组vector<int>stata(n+1,-1),初始化为-1，当求解一种情况的时候，先检查一下这种情况是否已经被求过了，如果求过了直接返回结果；如果没求过，就去求解，代码如下
2.记忆化搜索代码：
class Solution { public: int numTrees(int n) { vector<int> state(n + 1,-1); return dfs(state,n); } int dfs(vector<int>&state,int n) { int ans = 0; if(n == 0 || n == 1) return 1; else if(state[n] != -1) return state[n]; for(int i = 1; i <= n; i++) { state[i-1] = dfs(state,i-1); state[n-i] = dfs(state,n-i); ans += state[i-1] * state[n-i]; } return ans; } };经过运行，我们发现优化之后的代码过了，而且速度还是可以。
3.动态规划方法：由上面的两种方法很容易理解动态规划的方法
f[i] : 表示以i为根节点组成的树的个数
G[n] : 表示n个节点组成的二叉树的个数 G[n] = f[1] + f[2] + ... + f[n]; 而f[i] = G[i-1] * G[n-i] ，和上面的推导一样 ==>G[n] = G[0]*G[n-1] + G[1]*G[n-2] + ....G[n-1]*G[0]
G[2] = f[1] + f[2] = G[0]*G[1] + G[1]*G[0]
G[3] = G[0]*G[2] + G[1]*G[1] + G[2]*G[0] 如果还是不太清楚的小伙伴请参考leetcode96的评论
class Solution { public: int numTrees(int n) { vector<int> G(n+1,0); G[0] = 1; G[1] = 1; for(int i = 2; i <= n; i++) { for(int j = 1; j <= i; j++) { G[i] += G[j-1]*G[i-j]; } } return G[n]; }
