需要知道，什么是二叉搜索树：比如说一个2为根的二叉搜索树，那么它的左边所有元素一定是小于2的，而右侧的所有元素一定是大于2的，书面的语言是如果左子树不为空，那么左子树的所有节点都小于根节点，如果右子树不为空，右子树的所有节点都大于根节点。

这道题目，让我们计算从1到n互不相同的二叉搜索树有多少种，只需要求出数目即可，不需要返回具体的树的排列，因此使用深度优先DFS算法去求出每一种大概率会超时，而且要排除重复情况，没那么好写。

感觉上这种复杂的dfs能解决的问题可以通过动态规划来写，我们可以试着找到一种关系式。比如我们需要求1到5的所有的二叉搜索树，其实等同于以1以2以3到以5为根节点的所有二叉搜索树的和，这和dfs去遍历所有结果似乎有相似的地方，接着考虑怎么求这些二叉树。

比如以1为根的二叉搜索树，由于二叉搜索树的性质，左边一定是比1要小的，右侧一定是比1要大的，因此可以判断左右子树节点的个数。而且以1为根的二叉搜索树数目等于左子树搜索树的数目乘以右子树搜索树的数目，也就是对应的0个节点的左子搜索树数目乘以3个节点的右搜索数的数目，这样我们就似乎把搜索树个数联系起来了。

一个二叉搜索树的所有数目，等于以它每个元素为根的二叉搜索树数目之和，以某个数为根的二叉搜索树的个数等于左子树个数乘以右子树个数，而左子树和右子树节点数目也是知道的，这里就可以写公式来动态规划啦

G(n) = fn(1)+fn(2)+fn(3)+…+fn(n)
Fn(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(n)是n个数目二叉搜索树的个数，fn是对应根的二叉搜索树的数目

有了这几个公式，我们就可以轻松地解出这道题目了，代码如下

需要注意的是初始化的问题，和边界的问题，我一开始偷懒不初始化0和1，直接初始化1的数组，但是后面是dp[i]+=dp[j-1]*dp[i-j]这时候就会出问题；边界问题是因为0和1已经初始化过了不需要再初始化不然会越界，所以从2开始，对于j来说，j可以从1到n，这里是i，所以写i+1，i解决的是从1到n的搜索树个数的问题，而j解决的是它内部的计算。

day2 end

好好好

day3捏？

师兄怎么转码了