0096.不同的二叉搜索树

func numTrees(n int) int {
	memo := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		memo[i] = make([]int, n+1)
	}
	var dfs func(l, r int) int
	dfs = func(l, r int) int {
		if l > r {
			return 1
		}
		if memo[l][r] != 0 {
			return memo[l][r]
		}
		ans := 0
		for i := l; i <= r; i++ {
			left, right := dfs(l, i-1), dfs(i+1, r)
			ans += left * right
		}
		memo[l][r] = ans
		return ans
	}
	return dfs(1, n)
}