揭秘：n对圆括号组成不同合法括号序列数量的卡特兰数解法

问题分析 这是一个经典的卡特兰数（Catalan number）应用问题。对于 `n` 对圆括号组成的不同合法括号序列的数量，其值等于第 `n` 个卡特兰数。 卡特兰数的递推公式为： $C_0 = 1$ $C_{n+1}=\sum_{i = 0}^{n}C_iC_{n - i}$，$n\geq0$ 也可以通过组合数公式直接计算： $C_n=\frac{C_{2n}^n}{n + 1}=\frac{(2n)!}{(n+1)!n!}$ 代码实现（Python） ```python def catalan_number(n): # 初始化一个长度为 n+1 的数组，用于存储卡特兰数 catalan = [0] * (n + 1) # 第 0 个卡特兰数为 1 catalan[0] = 1 # 计算第 1 到第 n 个卡特兰数 for i in range(1, n + 1): for j in range(i): # 根据递推公式计算卡特兰数 catalan[i] += catalan[j] * catalan[i - j - 1] return catalan[n] # 读取输入 n = int(input()) # 计算并输出结果 print(catalan_number(n)) ``` 复杂度分析 - 时间复杂度：$O(n^2)$，主要是双重循环的时间开销。 - 空间复杂度：$O(n)$，主要用于存储卡特兰数的数组。 测试 对于输入 `4`，程序将输出 `14`，与样例输出一致。 ######[AI问答 | 401点数解答 | 2025-12-13 10:27:43]