96不同的二叉搜索树.md

func numTrees(n int) int {
    // dp[i]为有i个节点时组成的二叉搜索树数量
    dp := make([]int, n+1)
    dp[0] = 1
    for i := 1; i <= n; i++ {
        for j := 1; j <= i; j++ {
            // 对于第i个节点，要考虑从1作为根节点到以i作为根节点的树的数量，所以要累加
            dp[i] += dp[j-1] * dp[i-j] // 一共i个节点，以j为根节点时，左子树有j-1个节点，右子树有i-j个节点
        }
    }
    return dp[n]
}