8.3 卡特蘭數與遞迴計數#

import math
from functools import lru_cache

# --- 方法一：遞迴（含記憶化） ---
@lru_cache(maxsize=None)
def catalan_rec(n):
    if n == 0:
        return 1
    return sum(catalan_rec(i) * catalan_rec(n - 1 - i) for i in range(n))

# --- 方法二：動態規劃填表 ---
def catalan_dp(N):
    c = [0] * (N + 1)
    c[0] = 1
    for n in range(1, N + 1):
        c[n] = sum(c[i] * c[n - 1 - i] for i in range(n))
    return c

# --- 方法三：封閉公式（大整數精確） ---
def catalan_formula(n):
    return math.comb(2 * n, n) // (n + 1)

c_dp = catalan_dp(20)
assert all(catalan_rec(i) == c_dp[i] == catalan_formula(i)
           for i in range(21))
print("前 10 個卡特蘭數:", c_dp[:10])
print("C(100) 的位數:", len(str(catalan_formula(100))))

# --- 驗證：暴力枚舉合法括號序列 ---
def count_valid_parens(n):
    def gen(prefix, open_cnt, close_cnt):
        if len(prefix) == 2 * n:
            return 1
        total = 0
        if open_cnt < n:
            total += gen(prefix + "(", open_cnt + 1, close_cnt)
        if close_cnt < open_cnt:
            total += gen(prefix + ")", open_cnt, close_cnt + 1)
        return total
    return gen("", 0, 0)

for n in [1, 2, 3, 4, 5]:
    brute = count_valid_parens(n)
    print(f"n={n}: 枚舉={brute}, 卡特蘭={catalan_formula(n)}")
    assert brute == catalan_formula(n)

# --- 應用：n 個節點的二元搜尋樹計數 ---
def count_bst(n):
    return catalan_formula(n)
print("10 個節點的相異 BST 樹數 =", count_bst(10))

# --- 遞迴計數的另一例：走格線不越過對角線 ---
def lattice_paths(n):
    """從 (0,0) 到 (n,n)，每步向右或向上，恆不越過 y=x"""
    return catalan_formula(n)