96。DifferentBinarySearchTreesTopics来源：LeetCodehttps://leetcode-cn.com/problems/unique-binary-search-treesTopics给定一个整数n，有多少个节点为1...n的二叉搜索树？示例：输入：3输出：5解释：给定n=3，有5棵结构不同的二叉搜索树：13321\///\321132//\2123解题思路：从题意可以看出动态规划。当给定有序序列1...n时，就构造了一个二叉搜索树。结合例子，可以得出的解法是：在区间[1-n]中，遍历每一个数i，以这个数为根，然后将i左边的序列作为左子树，而i右边的序列作为右子树。现在我们假设在给定的n个节点中，有一个数G(n)可以组成一棵二叉搜索树，以i为根的二叉搜索树的数目为f(i)。那么我们可以得到如下公式：G(n)=f(1)+f(2)+...+f(n-1)+f(n)也就是说，当需要序列1时。..n能组成多少颗二叉搜索树，需要得到f(i)的个数，(1<=i<=n)，然后累加结果。前面说过，如果i是根节点，那么i左边的序列就会作为左子树，i右边的序列就会作为右子树。这里，左子树的节点数为i-1，右子树的节点数为n-i，那么此时：f(i)=G(i-1)*G(n-i)注意这里是的，G(n)其中n代表数字，与序列的内容无关。因此，以上可以形成左子树，右子树的个数由其节点数决定。现在将f(i)应用于上面的公式并得到：G(n)=G(0)*G(n-1)+G(1)*G(n-2)+...+G(n-2)*G(1)+G(n-1)*G(0)其实这其实就是加泰罗尼亚数。有兴趣的可以了解一下（根据个人情况，下面的链接可以了解加泰罗尼亚语的具体信息）。https://en.wikipedia.org/wiki/Catalan_number（同上，来源：维基百科）https://baike.baidu.com/item/catalan（来源：百度百科）这里初始化，注意边界问题：当n=0时，表示为一棵空树，只有一种情况，所以G(0)=1；当n=1时，表示只有一个根，这里只有一种情况，此时G(1)=1。本题具体代码实现如下。代码实现类解决方案：defnumTrees(self,n:int)->int:dp=[0]*(n+1)#初始化dp[0]=1dp[1]=1foriinrange(2,n+1):forjinrange(i+1):#代入公式#注意这里是累加的dp[i]+=dp[j-1]*dp[i-j]returndp[-1]达到效果欢迎关注公众号【图书收藏】
