LeetCode 96 Unique Binary Search Trees：卡特蘭數計算 BST 數量

LeetCode 96 Unique Binary Search Trees：卡特蘭數計算 BST 數量

給定 n，求由 1..n 構成的不同二叉搜索樹數量。答案為第 n 個卡特蘭數。

動態規劃推導

以 i 為根，左子樹節點 1..i-1（i-1 個），右子樹 i+1..n（n-i 個）。

dp[n] = Σ dp[i-1] * dp[n-i]  (i=1..n)
dp[0] = dp[1] = 1

三種解法對比

1. DP 迭代 O(n²)

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

2. 卡特蘭數公式 O(n)

C(n) = (2n)! / (n! * (n+1)!) = C(2n, n) / (n+1)

// 防溢出計算
long long numTrees(int n) {
    long long res = 1;
    for (int i = 0; i < n; ++i) {
        res = res * 2 * (2*i + 1) / (i + 2); // 遞推公式
    }
    return res;
}

3. 遞歸 + 備忘錄 O(n²)

int numTrees(int n) {
    vector<int> memo(n + 1, -1);
    function<int(int)> dfs = [&](int n) {
        if (n <= 1) return 1;
        if (memo[n] != -1) return memo[n];
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            ans += dfs(i-1) * dfs(n-i);
        return memo[n] = ans;
    };
    return dfs(n);
}

卡特蘭數性質

遞推公式推導

C(0) = 1
C(n+1) = C(n) * 2(2n+1) / (n+2)

// 證明：
C(n) = (2n)! / (n!(n+1)!)
C(n+1) = (2n+2)! / ((n+1)!(n+2)!)
       = C(n) * (2n+2)(2n+1) / ((n+1)(n+2))
       = C(n) * 2(2n+1) / (n+2)

複雜度對比

擴展：BST 形態枚舉

若需生成所有 BST（LeetCode 95），用遞歸構造：

vector<TreeNode*> generate(int l, int r) {
    if (l > r) return {nullptr};
    vector<TreeNode*> ans;
    for (int i = l; i <= r; ++i) {
        auto left = generate(l, i-1);
        auto right = generate(i+1, r);
        for (auto L : left)
            for (auto R : right) {
                TreeNode* root = new TreeNode(i);
                root->left = L; root->right = R;
                ans.push_back(root);
            }
    }
    return ans;
}

此題是卡特蘭數最經典的應用之一，掌握其 DP 推導、封閉公式、遞推關係，對組合數學和樹形 DP 都有深刻啟發。