96. 不同的二叉搜索树

题目

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

难度：🌟🌟🌟

示例 1：

输入：n = 3
输出：5

示例 2：
输入：n = 1
输出：1

提示：

• 1 <= n <= 19

题解

假设给算法输入 n=5，也就是说用 {1,2,3,4,5} 这些数字去构造 BST。
如果固定3作为根节点，左子树节点就是 {1,2} 的组合，右子树就是 {4,5} 的组合。

那么 {1,2} 和 {4,5} 的组合有多少种呢？只要合理定义递归函数，这些可以交给递归函数去做。
这题存在重叠子问题，可以通过备忘录的方式消除冗余计算。

代码实现

// 备忘录，记录计算结果，防止超时
var memo [][]int

func numTrees(n int) int {
	// 备忘录初始化
	memo = make([][]int, n+1)
	for i := range memo {
		memo[i] = make([]int, n+1)
	}
	return build(1, n)
}

func build(lo, hi int) int {
	if lo > hi {
		return 1
	}
	if memo[lo][hi] != 0 { // 备忘录中存在，则直接使用
		return memo[lo][hi]
	}
	var res int
	for i := lo; i <= hi; i++ {
		leftNum := build(lo, i-1)
		rightNum := build(i+1, hi)
		res += leftNum * rightNum
	}
	memo[lo][hi] = res
	return res
}