1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// @Title: 不同的二叉搜索树 (Unique Binary Search Trees)
// @Author: 15816537946@163.com
// @Date: 2020-08-29 23:28:07
// @Runtime: 0 ms
// @Memory: 1.9 MB
func numTrees(n int) int {
	G := make([]int, n+1)
	G[0], G[1] = 1, 1
	for i := 2; i <= n; i++ {
		for j := 1; j <= i; j++ {
			G[i] += G[j-1] * G[i-j]
		}
	}
	return G[n]
}