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)
}