096 不同的二叉搜索树-中等

题目：

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

分析：

由于二叉搜索树的特殊性，我们可以知道：对于[1, n] 序列，如果选取 i 作为根节点，那么总的二叉搜索树的数目就是由 [1,i]组成的左子树 乘以 由 [i+1,n] 组成的右子树。

所以可以用动态规划来解决这个问题，其初值为:

g[0], g[1] = 1, 1

// 
func numTrees(n int) int {
    g := make([]int, n+1, n+1)
    g[0], g[1] = 1, 1
    for i := 2; i <=n; i++ {
        // 根节点为i，有多少种可能
        for j := 1; j <= i; j++ {
            g[i] += g[j-1] * g[i-j]
        }
    }
    return g[n]
}