一、问题描述

给定一个整数 $ n $，求由 $ 1 $ 到 $ n $ 为节点组成的不同的二叉搜索树（BST）的数量。

二、方案一：动态规划

1、思路

动态规划的核心思想是将问题分解为更小的子问题。对于这个问题，我们可以考虑以每个数字作为根节点，然后计算左子树和右子树的可能组合数。

• 定义一个数组 dp[i] 表示由 $ i $ 个节点组成的不同的二叉搜索树的数量。
• 对于每个数字 $ i $（从 1 到 $ n $），作为根节点，其左子树可以有 $ i-1 $ 个节点，右子树可以有 $ n-i $ 个节点。
• 因此，以 $ i $ 为根节点的二叉搜索树的数量为 dp[i-1] * dp[n-i]。
• 最终结果是所有这些可能性的总和。

2、代码实现

func numTrees(n int) int {
    dp := make([]int, n+1)
    dp[0], dp[1] = 1, 1
    for i := 2; i <= n; i++ {
        for j := 1; j <= i; j++ {
            dp[i] += dp[j-1] * dp[i-j]
        }
    }
    return dp[n]
}

3、复杂度分析

• 时间复杂度：O(n^2)，因为我们需要计算每个数字作为根节点的情况。
• 空间复杂度：O(n)，用于存储动态规划数组。

三、方案二：卡塔兰数

1、思路

这个问题实际上是一个经典的数学问题，其解是卡塔兰数。第 $ n $ 个卡塔兰数可以表示为： $$ C_n = \frac{1}{n+1} \binom{2n}{n} $$ 也可以递归地表示为： $$ C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i \cdot C_{n-i} $$

2、代码实现

func numTrees(n int) int {
    var catalan func(int) int
    catalan = func(n int) int {
        if n <= 1 {
            return 1
        }
        res := 0
        for i := 0; i < n; i++ {
            res += catalan(i) * catalan(n-i-1)
        }
        return res
    }
    return catalan(n)
}

3、复杂度分析

• 时间复杂度：O(n^2)，与方案一相同。
• 空间复杂度：O(n)，由于递归调用栈的深度。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
动态规划	O(n^2)	O(n)	直观，易于理解	需要额外的数组存储中间结果
卡塔兰数	O(n^2)	O(n)	数学上更优雅，不需要额外数组	递归可能导致较大的调用栈

两种方案在效率上相当，选择哪一种取决于个人偏好。动态规划更直观，而卡塔兰数方案在数学上更优雅。