hot100-不同的二叉搜索树

func numTrees(n int) int {
    // dp[i] 表示由 i 个节点（值从 1 到 i）能构成的不同二叉搜索树的个数
    dp := make([]int, n+1) // 创建长度为 n+1 的切片，索引 0..n
 
    // 基础情况：空树和只有一个节点的树都只有 1 种
    dp[0], dp[1] = 1, 1
 
    // 从 2 个节点开始，逐步计算到 n 个节点
    for i := 2; i <= n; i++ {
        // 枚举根节点的值 j，j 可以从 1 到 i
        for j := 1; j <= i; j++ {
            // 左子树有 j-1 个节点，右子树有 i-j 个节点
            // 左右子树的形态数相乘，得到以 j 为根的总数
            // 累加到 dp[i] 上，覆盖所有可能的根节点
            dp[i] += dp[j-1] * dp[i-j]
        }
    }
 
    // 返回 n 个节点的二叉搜索树总数
    return dp[n]
}