卡特兰数 leetcode_卡特兰数的应用

卡特兰数的应用

$Catala{n}_n$ 可以表示：

• $n$ 个结点的不同形态的二叉树的个数
• $n$ 对括号的合法括号序列的个数
• 长度为 $n$ 的入栈序列对应的合法出栈序列个数
• 通过链接顶点而将 $n+2$ 边的凸多边形分成三角形的方法个数
• $n+1$ 个叶子的满二叉树个数

卡特兰数

卡特兰数为（从零项开始）：$1,1,2,5,14,42,132,429,1430,4862,\cdots$

卡特兰数的递推公式的推导过程

我们从 n 对括号的合法括号序列的个数 入手

就拿 $5$ 对括号来说，可以分为 $5$ 个类型：

1. 最左边的左括号和第 $1$ 个右括号匹配
2. 最左边的左括号和第 $2$ 个右括号匹配
3. 最左边的左括号和第 $3$ 个右括号匹配
4. 最左边的左括号和第 $4$ 个右括号匹配
5. 最左边的左括号和第 $5$ 个右括号匹配

既然这 $5$ 对括号是合法的，就说明最左边的左括号就是第一位

也就是说，这对括号是最外层的

那么整个括号序列就被它分成了两部分

就拿 最左边的左括号和第 1 个右括号匹配 来说，这对括号里边有 $0$ 对括号，外边有 $4$ 对括号

$0$ 对括号的合法括号序列的个数是 $Catala{n}_0$，$4$ 对括号的合法括号序列的个数是 $Catala{n}_4$

根据乘法原理，这种情况的序列数量为 $Catanla{n}_0\cdot Catanla{n}_4$

同理，最左边的左括号和第 $k$ 个右括号匹配，序列数量为 $Catanla{n}_{k-1}\cdot Catanla{n}_{n-k}$

根据加法原理，$5$ 对括号的合法括号序列的个数为 $Catanla{n}_0\cdot Catanla{n}_4+Catanla{n}_1\cdot Catanla{n}_3+\dots +Catanla{n}_4\cdot Catanla{n}_0$

因此，我们推出 $n$ 对括号的合法括号序列的个数为 $Catanla{n}_0\cdot Catanla{n}_{n-1}+Catanla{n}_1\cdot Catanla{n}_{n-2}+\dots +Catanla{n}_{n-1}\cdot Catanla{n}_0$

代码实现卡特兰数的第 n 项

有一道洛谷上的题：P1044 [NOIP2003 普及组] 栈，因为卡特兰数的第 $n$ 项可以应用于长度为 $n$ 的入栈序列对应的合法出栈序列个数，所以这道题就是一道卡特兰数的模版题

这是注释版的代码：

#include <cstdio> #define N 105 using namespace std; typedef long long ll; int n; ll C[N]; int main() { 
    scanf("%d", &n); C[0] = 1; for(int i = 1; i <= n; ++i) // 枚举卡特兰数的第 i 项 for(int k = 1; k <= i; ++k) // 最左边的左括号和第 k 个有括号匹配 C[i] += C[k - 1] * C[i - k]; // 根据递推公式写出 printf("%lld\n", C[n]); return 0; } 

我的提交结果

尾声

如果这篇题解对您（或您的团队）有帮助的话，就帮忙点个赞，加个关注！

最后，祝您（或您的团队）在 OI 的路上一路顺风！！！

┬┴┬┴┤・ω・)ノ Bye~Bye~

今天的文章
卡特兰数 leetcode_卡特兰数的应用分享到此就结束了，感谢您的阅读。