卡特兰数详解（C++语言实现与算法入门指南）

卡特兰数的典型应用场景

• 合法的括号序列数量（如 n 对括号）
• n+1 个叶子节点的满二叉树数量
• n 个元素的出栈序列种数
• 凸多边形三角划分方式数量

C++ 实现卡特兰数的三种方法

方法一：递归法（简单但效率低）

直接根据递推公式实现，适合理解原理，但时间复杂度高（指数级）。

#include <iostream>using namespace std;long long catalanRecursive(int n) {    if (n <= 1) return 1;        long long res = 0;    for (int i = 0; i < n; i++) {        res += catalanRecursive(i) * catalanRecursive(n - 1 - i);    }    return res;}int main() {    int n = 5;    cout << "C_" << n << " = " << catalanRecursive(n) << endl;    return 0;}  

方法二：动态规划（推荐）

使用动态规划避免重复计算，时间复杂度 O(n²)，空间复杂度 O(n)。

#include <iostream>#include <vector>using namespace std;long long catalanDP(int n) {    vector<long long> dp(n + 1, 0);    dp[0] = dp[1] = 1;    for (int i = 2; i <= n; i++) {        for (int j = 0; j < i; j++) {            dp[i] += dp[j] * dp[i - 1 - j];        }    }    return dp[n];}int main() {    int n = 5;    cout << "C_" << n << " = " << catalanDP(n) << endl;    return 0;}  

方法三：利用组合公式（最高效）

直接使用组合数学公式 Cₙ = C(2n, n) / (n+1)，通过优化计算避免大数溢出。

#include <iostream>using namespace std;long long binomialCoeff(int n, int k) {    long long res = 1;    if (k > n - k) k = n - k; // 利用对称性    for (int i = 0; i < k; i++) {        res *= (n - i);        res /= (i + 1);    }    return res;}long long catalanFormula(int n) {    long long c = binomialCoeff(2 * n, n);    return c / (n + 1);}int main() {    int n = 5;    cout << "C_" << n << " = " << catalanFormula(n) << endl;    return 0;}  

总结

通过本教程，你已经掌握了卡特兰数的基本概念及其在C++算法中的三种实现方式。对于初学者，建议先理解递归思想；在实际编程中，优先使用动态规划或组合公式法以提高效率。无论你是准备面试还是学习组合数学，掌握递推公式和这些实现技巧都将大有裨益。

关键词回顾：卡特兰数、C++算法、递推公式、动态规划