LeetCode Unique BSTs：卡特兰数 DP 计算二叉搜索树数量

题目大意

给定 n，求由 1..n 构成的不同结构 BST 数量。n=3 时有 5 棵。

卡特兰数递推

以 i 为根：左子树 1..i-1（i-1 个节点），右子树 i+1..n（n-i 个节点）。
F(n) = Σ_{i=1}^n F(i-1) * F(n-i)，F(0)=F(1)=1。
即卡特兰数 C_n = (2n)!/((n+1)!n!)。

DP 实现

class Solution {
public:
    int numTrees(int n) {
        vector dp(n+1);
        dp[0] = dp[1] = 1;
        for (int i=2; i<=n; ++i) {
            dp[i] = 0;
            for (int j=1; j<=i; ++j)
                dp[i] += dp[j-1] * dp[i-j];
        }
        return dp[n];
    }
};

复杂度

• 时间：O(n²)
• 空间：O(n)

数学公式 O(n) 计算

long long numTrees(int n) {
    long long c = 1;
    for (int i=0; i

前几项
n=1:1, 2:2, 3:5, 4:14, 5:42, 6:132, 7:429, 8:1430, 9:4862, 10:16796...