卡特兰数详解（C语言实现卡特兰数的递归与动态规划算法）

在计算机科学和组合数学中，卡特兰数（Catalan Number）是一类非常重要的整数序列，广泛应用于括号匹配、二叉树计数、出栈序列等问题。本文将用通俗易懂的方式，带你从零开始理解卡特兰数，并使用C语言实现其计算方法，包括递归实现和更高效的动态规划方式。

什么是卡特兰数？

卡特兰数的前几项为：

C₀ = 1
C₁ = 1
C₂ = 2
C₃ = 5
C₄ = 14
C₅ = 42

它满足如下递推公式：

Cₙ = Σ (Cᵢ × Cₙ₋₁₋ᵢ)，其中 i 从 0 到 n−1

也可以用闭式公式表示：

Cₙ = (2n)! / ((n+1)! × n!)

卡特兰数详解（C语言实现卡特兰数的递归与动态规划算法）卡特兰数 C语言算法递归实现动态规划第1张

方法一：递归实现卡特兰数（简单但效率低）

最直观的方法是直接按照递推公式写一个递归函数。虽然代码简洁，但由于存在大量重复计算，时间复杂度高达 O(4ⁿ/n^(3/2))，只适合计算很小的 n。

#include <stdio.h>int catalan_recursive(int n) {    // 基础情况    if (n <= 1) {        return 1;    }    int res = 0;    for (int i = 0; i < n; i++) {        res += catalan_recursive(i) * catalan_recursive(n - 1 - i);    }    return res;}int main() {    int n = 5;    printf("C(%d) = %d\n", n, catalan_recursive(n));    return 0;}

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

为了避免重复计算，我们可以使用动态规划（Dynamic Programming）的思想，自底向上计算并存储中间结果。时间复杂度降为 O(n²)，空间复杂度为 O(n)。

#include <stdio.h>#include <stdlib.h>long catalan_dp(int n) {    long* dp = (long*)malloc((n + 1) * sizeof(long));    // 初始化基础情况    dp[0] = dp[1] = 1;    // 自底向上填表    for (int i = 2; i <= n; i++) {        dp[i] = 0;        for (int j = 0; j < i; j++) {            dp[i] += dp[j] * dp[i - 1 - j];        }    }    long result = dp[n];    free(dp);    return result;}int main() {    int n = 10;    printf("C(%d) = %ld\n", n, catalan_dp(n));    return 0;}