LeetCode 96 - 不同的二叉搜索樹數量（動態規劃）

問題描述

給定 n，求由 1...n 為節點構成的結構不同的二叉搜索樹（BST）數量。例如 n=3 時有 5 棵不同的 BST。

動態規劃分析

設 f(i) 為 i 個節點能構成的不同 BST 數。以 k 為根節點，左子樹由 1...k-1 構成（共 k-1 個節點），右子樹由 k+1...n 構成（共 n-k 個節點）。根據乘法原理：

f(n) = Σ_{k=1}^{n} f(k-1) * f(n-k)，其中 f(0)=1, f(1)=1。

這是經典的卡特蘭數遞推公式：C_n = (2n)! / ((n+1)! n!)。

代碼實現（C++）

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

優化：直接計算卡特蘭數

利用組合數公式 C_n = C(2n, n) / (n+1) 可在 O(n) 時間內計算，避免雙重循環。

long long numTrees(int n) {
    long long res = 1;
    for (int i = 0; i < n; i++) {
        res = res * 2 * (2*i + 1) / (i + 2); // 遞推公式：C_{i+1} = C_i * 2(2i+1)/(i+2)
    }
    return res;
}

總結

本質是卡特蘭數問題，動態規劃易於理解，組合數公式效率更高。面試中掌握兩種解法並說明關係加分。