卡特兰数详解（Python语言实现卡特兰数算法全攻略）

卡特兰数的数学公式

卡特兰数有多种定义方式，最常见的是以下两种：

1. 递推公式：
   C₀ = 1
   Cₙ = Σ (Cᵢ × Cₙ₋₁₋ᵢ)，其中 i 从 0 到 n−1
2. 闭式公式（组合公式）：
   Cₙ = (1 / (n + 1)) × C(2n, n) = (2n)! / ((n + 1)! × n!)

方法一：递归实现卡特兰数（适合理解原理）

这是最直观的方法，直接按照递推公式来写。但注意：效率较低，仅适用于小规模 n。

def catalan_recursive(n):    if n <= 1:        return 1    res = 0    for i in range(n):        res += catalan_recursive(i) * catalan_recursive(n - 1 - i)    return res# 测试for i in range(6):    print(f"C({i}) = {catalan_recursive(i)}")  

这段代码清晰地体现了递归实现卡特兰数的思想。但对于 n > 15 时，计算会变得非常慢，因为存在大量重复计算。

方法二：动态规划实现（高效推荐）

为了避免重复计算，我们可以使用动态规划（Dynamic Programming）来存储中间结果，大幅提升效率。

def catalan_dp(n):    if n <= 1:        return 1    # 创建 dp 数组，dp[i] 表示 C_i    dp = [0] * (n + 1)    dp[0], dp[1] = 1, 1        for i in range(2, n + 1):        for j in range(i):            dp[i] += dp[j] * dp[i - 1 - j]        return dp[n]# 测试for i in range(10):    print(f"C({i}) = {catalan_dp(i)}")  

这种方法的时间复杂度为 O(n²)，空间复杂度为 O(n)，非常适合实际应用，是动态规划卡特兰数的经典案例。

方法三：使用组合公式（数学优化）

如果你熟悉阶乘和组合数，可以直接用闭式公式计算，时间复杂度可降至 O(n)。

import mathdef catalan_formula(n):    return math.comb(2 * n, n) // (n + 1)# 测试for i in range(10):    print(f"C({i}) = {catalan_formula(i)}")  

注意：Python 3.8+ 支持 math.comb 函数。若版本较低，可手动实现组合数计算。

总结

通过本教程，你已经掌握了三种Python卡特兰数算法的实现方式：

• 递归法 —— 简单直观，适合学习理解
• 动态规划法 —— 高效实用，推荐用于实际项目
• 组合公式法 —— 数学最优，代码简洁

无论你是准备面试、做算法题，还是研究组合数学，卡特兰数都是一个必须掌握的重要知识点。希望这篇教程能帮你彻底搞懂它！

关键词回顾：卡特兰数、Python卡特兰数算法、递归实现卡特兰数、动态规划卡特兰数