leetcode-go/leetcode/medium/96.go

package main

// G(n) -> number of unique binary search tree of [1...n]
// F(i, n) -> ... of [1...n] while i is root
// G(n) = sum(F(i, n)), i ~ [1...n]
// F(i, n) = G(i-1) * G(n-i)
// So, G(n) = G(0) * G(n-1) + G(1) * G(n-2) + ... + G(n-1) * G(0)
func numTrees(n int) int {
	if n == 0 {
		return 1
	}
	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]
}

// func main() {
// 	fmt.Println(numTrees(0))
// 	fmt.Println(numTrees(1))
// 	fmt.Println(numTrees(7))
// }