最近看了一些 关于卡塔兰数的讲解 总结一下 卡特兰数 (总结的不好)
卡特兰数, 组合数学中的一种,其实 我们经常会遇到类似卡卡特兰数的问题, 例如排队问题, 对角线,多边形切割问题等等都是 卡特兰数,
前几项：1,2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,208012…
公式 C(n)=C(2n,n)/(n+1)
卡特兰数的
通项公式为:h(n)=C(n,2n)/(n+1)=(2n)!/((n!)*(n+1)!)
一维数组呈现方式 但是 只能到33 超过33 后会溢出
long long int c[45]
c[1]=1; for(i=2;i<40;i++) { c[i]=c[i-1]*(4*i-2)/(i+1); }
卡特兰 主要应用在
括号化问题,
矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)
((())) ()(()) ()()() (())() (()())
2 将多边行划分为三角形问题。
(1)将一个凸多边形区域分成三角形区域的方法数?
(2)类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少可能的道路？ 推出f(i,j)=f(i-1,j)+f(i,j-1)
故 可用两个for循环求解
dp[1][1]=1; for(i=2;i<40;i++) for(j=1;j<=i;j++) { dp[i][j]=dp[i-1][j]+dp[i][j-1]; }
(3)类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
3. 出栈次序问题。一个栈(无穷大)的进栈序列为1、2、3、...、n，有多少个不同的出栈序列?
类似的 50,100 元找零问题
4. 给顶节点组成二叉树的问题。
典型例题
2067 小兔子棋盘 http://acm.hdu.edu.cn/showproblem.php?pid=2067
hdu 1134 (类似于多边形分解) http://acm.hdu.edu.cn/showproblem.php?pid=1134
hdu1023 (栈的次序) http://acm.hdu.edu.cn/showproblem.php?pid=1023
hdu 1133 (买票问题) http://acm.hdu.edu.cn/showproblem.php?pid=1133
hdu 1130(二叉树) http://acm.hdu.edu.cn/showproblem.php?pid=1130
