Description
給定整數 n，回傳由 1 到 n 組成的所有結構不同的 BST 數量。
Example:
Input: n = 3 Output: 5
Intuition#
選定根節點後，左右子樹的組合數相乘；遍歷所有可能的根就是卡塔蘭數。
- 以 i 為根時，左子樹有 i-1 個節點，右子樹有 n-i 個節點
- 左右子樹的結構數量相互獨立，所以相乘
- G(n) = sum(G(i-1) * G(n-i)) for i in 1..n，這就是卡塔蘭數
Approaches#
1: DP#
- 概念: 自底向上計算 G(0) 到 G(n)，G(n) = sum(G(i-1) * G(n-i))
- 時間複雜度:
O(n^2) - 空間複雜度:
O(n)
class Solution {
fun numTrees(n: Int): Int {
val dp = IntArray(n + 1)
dp[0] = 1
dp[1] = 1
for (i in 2..n) {
for (j in 1..i) {
dp[i] += dp[j - 1] * dp[i - j]
}
}
return dp[n]
}
}⭐ 2: 卡塔蘭數公式#
- 概念: 直接用卡塔蘭數的遞推公式 C(n) = C(n-1) * 2(2n-1) / (n+1)
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun numTrees(n: Int): Int {
var catalan = 1L
for (i in 1 until n) {
catalan = catalan * 2 * (2 * i + 1) / (i + 2)
}
return catalan.toInt()
}
}卡塔蘭數的常見應用
卡塔蘭數 C(n) 出現在很多組合問題中：
- n 個節點的不同 BST 結構數
- n 對括號的合法組合數
- n+1 個矩陣連乘的不同括號化方式
- 從 (0,0) 到 (n,n) 不越過對角線的路徑數
🔑 Takeaways#
- Pattern: BST 計數問題 = 卡塔蘭數，核心是根的選擇將問題分解為左右獨立子問題
- 關鍵技巧: DP 解法直觀易懂，公式解法效率更高但需要記住卡塔蘭數遞推式