C a t a l a n n Catalan_n Catalann? 可以表示:
- n n n 个结点的不同形态的二叉树的个数
- n n n 对括号的合法括号序列的个数
- 长度为 n n n 的入栈序列对应的合法出栈序列个数
- 通过链接顶点而将 n + 2 n+2 n+2 边的凸多边形分成三角形的方法个数
- n + 1 n+1 n+1 个叶子的满二叉树个数
卡特兰数为(从零项开始): 1 , 1 , 2 , 5 , 14 , 42 , 132 , 429 , 1430 , 4862 , ? 1,1,2,5,14,42,132,429,1430,4862,\cdots 1,1,2,5,14,42,132,429,1430,4862,?
我们从 n 对括号的合法括号序列的个数
入手
就拿 5 5 5 对括号来说,可以分为 5 5 5 个类型:
既然这 5 5 5 对括号是合法的,就说明最左边的左括号就是第一位
也就是说,这对括号是最外层的
那么整个括号序列就被它分成了两部分
就拿 最左边的左括号和第 1 个右括号匹配
来说,这对括号里边有
0
0
0 对括号,外边有
4
4
4 对括号
0 0 0 对括号的合法括号序列的个数是 C a t a l a n 0 Catalan_0 Catalan0?, 4 4 4 对括号的合法括号序列的个数是 C a t a l a n 4 Catalan_4 Catalan4?
根据乘法原理,这种情况的序列数量为 C a t a n l a n 0 ? C a t a n l a n 4 Catanlan_0\cdot Catanlan_4 Catanlan0??Catanlan4?
同理,最左边的左括号和第 k k k 个右括号匹配,序列数量为 C a t a n l a n k ? 1 ? C a t a n l a n n ? k Catanlan_{k-1}\cdot Catanlan_{n-k} Catanlank?1??Catanlann?k?
根据加法原理, 5 5 5 对括号的合法括号序列的个数为 C a t a n l a n 0 ? C a t a n l a n 4 + C a t a n l a n 1 ? C a t a n l a n 3 + … + C a t a n l a n 4 ? C a t a n l a n 0 Catanlan_0\cdot Catanlan_4+Catanlan_1\cdot Catanlan_3+\ldots +Catanlan_4\cdot Catanlan_0 Catanlan0??Catanlan4?+Catanlan1??Catanlan3?+…+Catanlan4??Catanlan0?
因此,我们推出 n n n 对括号的合法括号序列的个数为 C a t a n l a n 0 ? C a t a n l a n n ? 1 + C a t a n l a n 1 ? C a t a n l a n n ? 2 + … + C a t a n l a n n ? 1 ? C a t a n l a n 0 Catanlan_0\cdot Catanlan_{n-1}+Catanlan_1\cdot Catanlan_{n-2}+\ldots +Catanlan_{n-1}\cdot Catanlan_0 Catanlan0??Catanlann?1?+Catanlan1??Catanlann?2?+…+Catanlann?1??Catanlan0?
有一道洛谷上的题:P1044 [NOIP2003 普及组] 栈,因为卡特兰数的第 n n n 项可以应用于长度为 n 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~