Medium
96. Unique Binary Search Trees
mathdynamic-programmingtreebinary-search-treebinary-tree
解題說明
Unique Binary Search Trees
題目描述：
給定整數 n，計算由 1 到 n 組成的結構唯一的二元搜尋樹（BST）有多少棵。
解題思路：
這是經典的 Catalan 數問題。定義 dp[i] 為 i 個節點能組成的不同 BST 數量。
對於 n 個節點，選擇任一值 k 作為根：
- 左子樹有
k-1個節點 →dp[k-1]種結構 - 右子樹有
n-k個節點 →dp[n-k]種結構
因此遞推公式為：
dp[n] = Σ dp[k-1] * dp[n-k]，k 從 1 到 n。
基礎情況：dp[0] = dp[1] = 1（空樹和單節點各一種）。
這正是 Catalan 數的遞推定義：C(n) = Σ C(i) * C(n-1-i)。
C++ 解法
複雜度分析
時間複雜度：O(n²) — 外層迴圈 n 次，內層迴圈平均 n/2 次。
空間複雜度：O(n) — dp 陣列大小為 n+1。
虛擬碼
1. Create dp array of size n+1, initialized to 0
2. Set dp[0] = 1, dp[1] = 1
3. For i from 2 to n:
a. For k from 1 to i:
dp[i] += dp[k-1] * dp[i-k]
4. Return dp[n]其他解法
Catalan 數公式 O(n)：直接用公式 C(n) = C(2n, n) / (n+1) = (2n)! / ((n+1)! * n!)。可逐步計算避免溢位：result = result * 2*(2*i+1) / (i+2)。時間 O(n)，空間 O(1)。數學上更優，但需注意整數溢位問題。
記憶化遞迴：直接按 Catalan 數遞推式實作 top-down 遞迴 + 快取。時間空間與 DP 相同，但概念上更直覺——選根、分左右、組合。適合作為理解問題結構的起點。
延伸思考
- 如何從「計算數量」延伸到「生成所有結構」？（LeetCode 95）
- Catalan 數還有哪些組合問題的應用？（括號匹配、路徑不穿越對角線等）
- 若 n 可達 10^9，能否用 O(n) 甚至 O(1) 的方式求解？需要考慮什麼數學工具？