1、题目描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：
2、分析
2.0、基础知识补齐
（1）二叉搜索树(BST)
既然搜索肯定就需要有序，有序的二叉树。 没啥可说的。
（2）树形结构
①构建树的时候都是要先明确根节点，然后递归地构建左右子树！！！！！
②树形结构，一般都是左/右子树可以抽象为范围更小的子问题。
2.1、本题思路
弄清楚两个关键点：
对于上述n=3的场景。
（1）假设G(n)表示n个节点构成的BST个数，h(1)/h(2)……h(n)表示以1~n为头结点的二叉树种类数，显然有： G(n) = h(1) + h(2) + h(3)
（2）接下来分析以i为根节点的BST个数要如何确定？
对于树类问题我们要去递归地分析左右子树。显然，对于以i为根节点的BST数 h(i)=左子树种类*右子树种类。集合BST特性知:
(1)根节点是1。左子树0节点的情况 * 右子树2节点的情况
(2)根节点是2。左子树1节点的情况 * 右子树1节点的情况
(3)根节点是3。左子树2节点的情况 * 右子树0节点的情况
仔细一看这不就是把n=3的问题转换成n=0/1/2的问题了吗。
即：dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]。
（3）推广一下，n个节点对应的BST种类数为就是依次选取1~n作为根节点的种类数相加：
dp[n] = dp[0]*dp[n-1]+dp[1]*dp[n-2]+…dp[j-1]*dp[n-j]+dp[j]*dp[n-j-1]+…+dp[n-1]*dp[0]
上述结论中虽然拆解后的子问题和实际子问题元素并不一致，没影响吗？
我们讨论下以1为根节点的情况。
此时其右子树是由{2,3}两个数构成的BST.其实 这里的右子树{2,3}完全可以看成{1,2}。
因为{1,2}构成的BST和{2,3}构成的BST的个数是完全一样的。这里看的是结构布局而不是数值，所以{2,3}和{1,2}构成的BST在种类数上肯定是完全一致的。
所以，我们也就可以将此时{2,3}构成的右子树种类数就视为n=2情况下BST的种类数，也就这么递归起来了。
2.2、规律找到后明确动规五部曲
(1)dp数组及含义
dp[i]就表示i个节点构成的BST种类数。
(2)动态转义方程
①依次以1~n作为根节点,的种类相加。
dp[n] = dp[0]*dp[n]+dp[1]*dp[n-1]+dp[2]*dp[n-2]+……dp[j]*dp[n-j]+……+dp[n]*dp[0]
(3)dp数组的初始化
dp[0] = 1 #空也是可以认为成一种树
dp[1] = 1 #一个元素可以构成一种树。其实dp[1]就已经可以用递归公式递推得到了。
(4)遍历顺序
从前往后。最终返回的结果就是dp[n]。
(5)打印dp
3、实现代码
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
/*
这里确实要两层循环。举个例子：
在n为5的情况下你不能上来就计算dp[5];因为初始化有的只是dp[0],想得到dp[5]就要在知道dp[0]的情况下
依次计算dp[1]、dp[2]、dp[3]、dp[4]、dp[5]。
*/
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1, 0);
dp[0] = 1;
//dp[0]已经有了。接下来依次得到dp[1]、dp[2]、dp[i]。
for (int i = 1; i <= n; i++){
//对于一个具体的dp[1]、dp[2]、dp[i]我们是需要按照前述转义方程累加计算得到的。
for (int j = 0; j < i; j++){
dp[i] += dp[j]*dp[i-j-1];
cout << "dp[" << i << "]:" << dp[i] << endl;
}
}
return dp[n];
}
};
int main()
{
Solution s1;
int n = 3;
cout << s1.numTrees(n) << endl;
}
