每日算法 — 使用java实现卡特兰数：递归与动态规划的组合计数

卡特兰数（Catalan Number）是组合数学中最经典、最美丽的数列之一。它出现在括号的合法匹配、二叉树计数、出栈序列、网格路径等众多场景中。本文将用Java完整实现卡特兰数的多种求解方式，从递归定义到动态规划优化，再到大数处理，带你深入理解这一组合数学的核心工具。

一、问题引入：合法括号序列

给定 n 对括号，能组成多少种合法的括号序列？

例如 n=3 时，合法序列有 5 种：

((()))  (()())  (())()  ()(())  ()()()

这个数量恰好就是第 3 个卡特兰数 C₃ = 5。

二、卡特兰数的数学定义

卡特兰数的递推公式：

C₀ = 1
Cₙ₊₁ = Σ(i=0 to n) Cᵢ × Cₙ₋ᵢ

封闭形式（利用组合数）：

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

前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

三、递归实现（含记忆化）

直接使用递推公式，时间复杂度 O(n²)，空间复杂度 O(n)。

import java.util.Arrays;

/**
 * 卡特兰数 - 记忆化递归实现
 * 时间复杂度: O(n²)
 * 空间复杂度: O(n)
 */
public class CatalanMemoization {

    private long[] memo;

    /**
     * 计算第n个卡特兰数
     * @param n 非负整数
     * @return 第n个卡特兰数的值
     */
    public long catalan(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        memo = new long[n + 1];
        Arrays.fill(memo, -1);
        return compute(n);
    }

    private long compute(int n) {
        if (n == 0 || n == 1) return 1;
        if (memo[n] != -1) return memo[n];

        long sum = 0;
        // Cₙ = Σ Cᵢ × Cₙ₋₁₋ᵢ  (i从0到n-1)
        for (int i = 0; i < n; i++) {
            sum += compute(i) * compute(n - 1 - i);
        }
        memo[n] = sum;
        return sum;
    }

    public static void main(String[] args) {
        CatalanMemoization solver = new CatalanMemoization();
        System.out.println("前15个卡特兰数（记忆化递归）:");
        for (int i = 0; i <= 15; i++) {
            System.out.printf("C(%2d) = %d%n", i, solver.catalan(i));
        }
    }
}

四、动态规划实现

自底向上填表，避免递归栈开销，同样 O(n²) 时间，O(n) 空间。

/**
 * 卡特兰数 - 动态规划实现
 * dp[i] 表示第i个卡特兰数
 */
public class CatalanDP {

    /**
     * 动态规划计算前n+1个卡特兰数
     */
    public long[] catalanDP(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");

        long[] dp = new long[n + 1];
        dp[0] = 1; // C₀ = 1

        // 按顺序计算 C₁ 到 Cₙ
        for (int i = 1; i <= n; i++) {
            long sum = 0;
            // Cᵢ = Σ dp[j] × dp[i-1-j]  (j从0到i-1)
            for (int j = 0; j < i; j++) {
                sum += dp[j] * dp[i - 1 - j];
            }
            dp[i] = sum;
        }
        return dp;
    }

    public static void main(String[] args) {
        CatalanDP solver = new CatalanDP();
        long[] result = solver.catalanDP(15);

        System.out.println("前16个卡特兰数（动态规划）:");
        for (int i = 0; i < result.length; i++) {
            System.out.printf("C(%2d) = %d%n", i, result[i]);
        }
    }
}

五、组合数公式实现（O(n)时间）

利用 Cₙ = C(2n, n) / (n+1)，可以在 O(n) 时间内计算。

import java.math.BigInteger;

/**
 * 卡特兰数 - 组合数公式实现（支持大数）
 * Cₙ = C(2n, n) / (n+1)
 * 时间复杂度: O(n)
 * 空间复杂度: O(1)
 */
public class CatalanCombinatorics {

    /**
     * 使用BigInteger支持大数计算
     */
    public BigInteger catalanBig(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");

        // 计算组合数 C(2n, n)
        BigInteger comb = BigInteger.ONE;
        // C(2n, n) = (2n × (2n-1) × ... × (n+1)) / n!
        for (int i = 1; i <= n; i++) {
            comb = comb.multiply(BigInteger.valueOf(n + i));
            comb = comb.divide(BigInteger.valueOf(i));
        }
        // Cₙ = C(2n, n) / (n+1)
        return comb.divide(BigInteger.valueOf(n + 1));
    }

    /**
     * 64位整数版本（仅适用于小n，n<=33时不会溢出）
     */
    public long catalanLong(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        if (n > 33) throw new IllegalArgumentException("n too large for long");

        long result = 1;
        for (int i = 0; i < n; i++) {
            result = result * 2 * (2 * i + 1) / (i + 2);
        }
        return result;
    }

    public static void main(String[] args) {
        CatalanCombinatorics solver = new CatalanCombinatorics();

        System.out.println("前20个卡特兰数（组合数公式 + BigInteger）:");
        for (int i = 0; i <= 20; i++) {
            System.out.printf("C(%2d) = %s%n", i, solver.catalanBig(i).toString());
        }

        System.out.println("\n验证 n=33 以内的long精度:");
        for (int i = 30; i <= 33; i++) {
            System.out.printf("C(%2d) = %d%n", i, solver.catalanLong(i));
        }
    }
}

六、应用场景：出栈序列计数

问题：n 个不同元素按顺序入栈，有多少种不同的出栈顺序？

答案：恰好为第 n 个卡特兰数 Cₙ。

import java.util.ArrayList;
import java.util.List;

/**
 * 出栈序列生成器 - 卡特兰数的经典应用
 * 使用回溯法生成所有合法的出栈序列
 */
public class StackSequenceGenerator {

    private List<String> result;

    /**
     * 生成n个元素的合法出栈序列
     * @param n 元素个数
     * @return 所有合法出栈序列列表
     */
    public List<String> generateSequences(int n) {
        result = new ArrayList<>();
        char[] sequence = new char[2 * n];
        backtrack(0, 0, 0, n, sequence);
        return result;
    }

    /**
     * 回溯生成括号/出栈序列
     * @param pos 当前位置
     * @param open 已放置的左括号数（入栈次数）
     * @param close 已放置的右括号数（出栈次数）
     * @param n 总对数
     * @param seq 当前序列
     */
    private void backtrack(int pos, int open, int close, int n, char[] seq) {
        if (pos == 2 * n) {
            result.add(new String(seq));
            return;
        }
        // 还可以入栈（放左括号）
        if (open < n) {
            seq[pos] = '('; // 表示入栈
            backtrack(pos + 1, open + 1, close, n, seq);
        }
        // 还可以出栈（放右括号），前提是栈不为空
        if (close < open) {
            seq[pos] = ')'; // 表示出栈
            backtrack(pos + 1, open, close + 1, n, seq);
        }
    }

    public static void main(String[] args) {
        StackSequenceGenerator generator = new StackSequenceGenerator();

        for (int n = 1; n <= 4; n++) {
            List<String> sequences = generator.generateSequences(n);
            System.out.printf("n=%d, 共 %d 种出栈序列 (C%d=%d):%n", 
                n, sequences.size(), n, new CatalanCombinatorics().catalanBig(n));
            for (String seq : sequences) {
                System.out.println("  " + seq);
            }
            System.out.println();
        }
    }
}

七、应用场景：二叉搜索树计数

n 个不同节点能构造多少种不同的二叉搜索树（BST）？答案同样是 Cₙ。

/**
 * 计算n个节点的不同BST数量
 * 递推: G(n) = Σ G(i-1) × G(n-i)  (i从1到n)
 * 这与卡特兰数的递推完全一致
 */
public class BSTCounter {

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int nodes = 2; nodes <= n; nodes++) {
            for (int root = 1; root <= nodes; root++) {
                int leftTrees = dp[root - 1];   // 左子树节点数 = root-1
                int rightTrees = dp[nodes - root]; // 右子树节点数 = nodes-root
                dp[nodes] += leftTrees * rightTrees;
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        BSTCounter counter = new BSTCounter();
        System.out.println("n个节点可构造的BST数量:");
        for (int i = 0; i <= 10; i++) {
            System.out.printf("n=%2d -> %d 种%n", i, counter.numTrees(i));
        }
    }
}

八、复杂度分析

九、总结

卡特兰数是连接递归、动态规划与组合数学的桥梁。掌握它不仅意味着记住一个公式，更重要的是理解其背后的”分裂-组合”思想：一个大问题可以分解为左右两个独立子问题的组合。这一思想在二叉树、括号匹配、出栈序列等无数场景中都有体现，是算法学习的重要里程碑。