卡特兰数

一句话说明

卡特兰数最常出现在“结构合法但不能交叉冲突”的计数题里，比如合法括号、BST 结构数、栈合法出栈序列。

什么时候该警觉它

如果题目长得像下面这些，先怀疑是不是卡特兰数：

• n 对括号有多少种合法写法
• n 个节点能形成多少种不同 BST
• 多边形三角剖分有多少种
• 栈合法出栈序列有多少种

最核心的公式

第 n 个卡特兰数：

Cat(n) = C(2n, n) / (n + 1)

也常写成：

Cat(n) = C(2n, n) - C(2n, n+1)

前几项是：

1, 1, 2, 5, 14, 42, ...

为什么递推长这样

另一个更适合 DP 的写法是：

Cat(n) = Cat(0)Cat(n-1) + Cat(1)Cat(n-2) + ... + Cat(n-1)Cat(0)

它的直觉非常像“选根节点分左右结构”：

• 左边用了 i 个元素
• 右边就用了 n-1-i 个元素
• 左右方案数相乘，再把所有 i 累加

Go 模板：DP 递推

func CatalanDP(n int) int {
    dp := make([]int, n+1)
    dp[0] = 1
 
    for nodes := 1; nodes <= n; nodes++ {
        for leftSize := 0; leftSize < nodes; leftSize++ {
            rightSize := nodes - 1 - leftSize
            dp[nodes] += dp[leftSize] * dp[rightSize]
        }
    }
 
    return dp[n]
}

Go 模板：组合数公式

func CatalanFormula(n int) int {
    return Comb(2*n, n) / (n + 1)
}
 
func Comb(n, k int) int {
    if k < 0 || k > n {
        return 0
    }
    if k > n-k {
        k = n - k
    }
 
    result := 1
    for i := 1; i <= k; i++ {
        result = result * (n - k + i) / i
    }
    return result
}

两种写法怎么选

用 DP

• 更容易理解结构来源
• 适合题目就是在做递推

用公式

• 写法更短
• 直接求值更快

如果题目还要求模运算，通常要结合 组合数取模与Lucas定理。

一个最典型的映射

LeetCode 96 不同的二叉搜索树：

• 固定某个值做根
• 左边是一个子问题
• 右边也是一个子问题
• 两边方案数相乘后累加

这就是标准卡特兰递推。

易错点

卡特兰数最容易错的地方

• Cat(0) = 1，不是 0。
• 递推里右边规模是 n-1-leftSize，别少减那个根节点。
• 组合数公式里除的是 n+1，不是 n。

复杂度

方法	时间复杂度	空间复杂度
DP	O(n^2)	O(n)
公式	取决于组合数实现	通常 O(1) 额外

相关笔记

• 组合数取模与Lucas定理
• 二维DP

---

返回：数学算法