不同的二叉搜索树题目链接：https://leetcode-cn.com/problems/unique-binary-search-trees给定一个整数n，求一棵由1...n个节点组成的二叉树有多少种搜索类型有树吗？例：这个题目的描述很短，但是估计大部分同学看完之后都是一头雾水。我们怎么算呢？关于什么是二叉搜索树，之前我已经详细讲解了二叉树的话题，大家也可以看看这个二叉树：二叉搜索树登场！我们再回顾一下。了解二叉搜索树后，我们先举几个例子，画图，看看有没有规律，如图：当n为1时，不同的二叉搜索树有一棵树，有两棵当n为2的树，这个很直观。不同的二叉搜索树1看当n为3时，有什么情况。当1为头节点时，其右子树有两个节点。看看这两个节点的布局是不是和n为2时两棵树的布局一样！（可能有同学会问，布局不一样，节点值也不一样。别忘了我们是在找不同树的个数，不需要列出所有的搜索树，所以我们不用关心它们具体值的区别）当3为头节点时，它的左子树有两个节点，看看这两个节点的布局，是不是和n时两棵树的布局一样是2！当2为头节点时，左右子树都只有一个节点。布局和n为1时只有一棵树的布局一样吗？当我们发现这一点时，我们实际上发现了重叠子问题。其实我们发现可以用dp[1]和dp[2]推导出dp[3]的某种方式。这么一想，这个话题就有了头绪。dp[3]，即元素1为头结点搜索树数+元素2为头结点搜索树数+元素3为头结点搜索树数元素1为头结点搜索树数=右子树中元素为2的搜索树的个数*左子树中元素为0的搜索树的个数元素为3的搜索树的个数即头节点处搜索树的个数=搜索树的个数右子树中有0个元素*左子树中有2个元素的搜索树的数量有2个元素的搜索树的数量是dp[2]。具有1个元素的搜索树的数量是dp[1]。具有0个元素的搜索树的数量是dp[0]。所以dp[3]=dp[2]*dp[0]+dp[1]*dp[1]+dp[0]*dp[2]如图：不同的二叉搜索树2这时候我们递归关系找到了，我们再结合动态规则的五个部分来系统分析一下。1、确定dp数组（dp表）及下标dp[i]的含义：从1到i的节点组成的二叉搜索树的个数为dp[i]。也可以这样理解，i的不同元素节点组成的二叉搜索树的个数为dp[i]，都是相同的。如果下面的分析不清楚，我们再回忆一下dp[i]的定义2.确定递归公式上面的分析其实已经看出了递归关系，dp[i]+=dp[以j开头的个数节点左子树中的节点数]*dp[以j为头节点的右子树节点数]j相当于头节点的元素，从1遍历到i。于是递推公式：dp[i]+=dp[j-1]*dp[i-j];,j-1是左子树节点的个数其中j为头节点,i-j是以j为头节点的右子树节点子树节点的个数3.如何初始化dp数组,只需要初始化dp[0]，推导的基础是dp[0]。那么dp[0]应该是什么呢？根据定义，空节点也是二叉树和二叉搜索树，这是有道理的。由递推公式dp[以j为头节点的左子树节点数]*dp[以j为头节点的右子树节点数]，以j为头节点的左子树节点数为0,还需要dp[以j为头节点的左子树节点的个数]=1，否则相乘的结果会变成0。所以初始化dp[0]=14。确定遍历顺序，遍历的个数必须先遍历节点。从递归公式：dp[i]+=dp[j-1]*dp[i-j]，可以看出节点数为i的状态是依赖于之前节点数的状态我。然后遍历i中的每一个数作为头节点的状态，用j遍历。代码如下：for(inti=1;i<=n;i++){for(intj=1;j<=i;j++){dp[i]+=dp[j-1]*dp[i-j];}}5。比如推导dp数组n为5时的dp数组状态，如图：不同的二叉查找树3当然，如果你自己画个例子，基本上可以举个例子直到n为3。当n是4，画图已经搞定了，比较麻烦。我把n为5的情况列了出来，这样大家在调试代码的时候，可以把dp数组敲出来，看看是哪里出了问题。经过以上分析，C++代码如下：classSolution{public:intnumTrees(intn){vector
