刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/unique-binary-search-trees/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

思路

动态规划

类似问题其实有不少，求解不同二叉树的个数的基本思路依据就是

我们在 n 个节点中，任意选取一个假定为根节点，然后用左右两边的数字分别构成左右子树，以此类推的构造出二叉树，就能够覆盖不同的情况了

所以就有了如下动态规划思路：

• dp[i] 意为 i 个节点组成的二叉搜索树的个数
• 初始化 dp[0], dp[1] = 1, 1
• 动态方程为 dp[i] = dp[j-1] * dp[i-j]，含义如下：
  • 共i个节点，以j为根节点
  • 左子树有j-1个节点，可形成dp[j-1]种
  • 右子树有i-j个节点，可形成dp[i-j]种

数学

这个是官方题解中给出的方法，上述动规的算法其实已经有了公式，所以会非常简单，直接计算即可：

思路大体就是这样了，没太多好说的了。

代码

func numTrees(n int) int {
	// dp[i] 意为 i 个节点组成的二叉搜索树的个数
	dp := make([]int, n+1)
	// 初始化
	dp[0], dp[1] = 1, 1
    // dp[i] = dp[j-1] * dp[i-j] 
    // 共i个节点，以j为根节点
    // 左子树有j-1个节点，可形成dp[j-1]种
    // 右子树有i-j个节点，可形成dp[i-j]种
	for i := 2; i <= n; i++ {
		for j := 1; j <= i; j++ {
			dp[i] += dp[j-1] * dp[i-j]
		}
	}
	return dp[n]
}