数组实现卡特兰数的核心是用一维数组catalan[i]存储cᵢ（i从0起），初始化catalan[0]=1，再按递推式catalan[i]=Σₖ₌₀ⁱ⁻¹ catalan[k]×catalan[i−1−k]迭代填充；亦可用线性公式catalan[i]=catalan[i−1]×(4i−2)/(i+1)优化至o(n)时间，需注意整除顺序与数据溢出处理。

用数组实现卡特兰数生成，核心是把递推过程“落地”为线性存储与迭代计算。它不依赖递归调用栈，避免重复子问题，适合批量预处理（比如打表查值、做ACM预计算），也便于后续直接索引使用。

用一维数组存前n项卡特兰数

定义 catalan[i] 表示第 i 项卡特兰数 Cᵢ（i 从 0 开始）。已知 C₀ = 1，其余按递推式逐项填充：

• catalan[0] = 1
• 对每个 i ≥ 1，执行 catalan[i] = Σⱼ₌₀ⁱ⁻¹ catalan[j] × catalan[i−1−j]
• 即：用已算出的 0 到 i−1 项，两两配对相乘后累加

例如算 C₃：catalan[3] = C₀C₂ + C₁C₁ + C₂C₀ = 1×2 + 1×1 + 2×1 = 5。

注意整数溢出与数据类型选择

卡特兰数增长极快（C₂₀ ≈ 6.56×10¹²，C₃₀ 已超 10³⁰），普通 int 或 long long 很快溢出：

• n ≤ 18：可用 unsigned long long（最大约 1.8×10¹⁹）
• n ∈ [19, 35]：推荐用 __int128（GCC 支持）或高精度整数类
• n > 35：必须用字符串/数组模拟大数乘除，如 HDU1023 那类题需存每位数字

若只需求模结果（如模 10⁹+7），可在每次乘加后取模，全程用 int 即可。

优化：改用线性递推公式减少嵌套循环

原始递推是 O(n²) 时间，但卡特兰数满足更高效的线性递推关系：

Cₙ = Cₙ₋₁ × (4n − 2) / (n + 1)

• 从 C₀ = 1 出发，每步只需一次乘、一次除
• 关键点：除法必须整除（数学上恒成立），编程中要保证先乘后除，避免截断误差
• 示例代码片段（无模）：

catalan[0] = 1;
for (int i = 1; i   catalan[i] = catalan[i-1] * (4*i - 2) / (i + 1);
}

实战中如何组织变量与复用结构

在算法题或工程模块中，建议封装为静态初始化结构：

• 声明全局/静态数组 long long C[101]（覆盖常见 n≤100 场景）
• 配合 init_catalan() 函数一次性预计算，main 中直接查表
• 若需多组输入（如洛谷 P1044），打表比每次重算快一个数量级
• 搭配组合数数组（如 C[n][k]）时，可共用同一阶乘预处理模块，节省空间

这种数组驱动方式，把抽象的组合意义（如合法括号数、BST形态数）转为可索引、可调试、可批量验证的具体数值序列。