问题描述:求1,2,3,4,5,6,7,按顺序入栈,3第一个出栈的出栈序列数 方法:枚举最后一个出栈的数,递推求解 g[i]表示方案数 f[i]表示1——i按顺序入栈的出栈序列数 铺垫:1——i按顺序入栈的出栈序列数为卡特兰数:C(2n,n)/(n+1)   1 2 3 g[3]=1 1 2 3 4  最后一个出栈的只可能有1,4 g[4]=f[2]+g[3]*f[0] g[5]+f[3]+g[3]*f[1]+g[4]*f[0] …… 所以g[7]=90  

2018年10月12日 0条评论 0点热度 阅读全文

这种问题是一个经典卡特兰数的问题,它的结果序列是完全符合卡特兰数的序列的,那么就需要分析一下为什么了。 首先,对这个问题的描述是,现在有一个凸多边形,连接不相邻的结点将其剖分为三角形,有多少种连接方法? 先看下面几张图: 四条边,两种剖分方法 五条边,五种剖分方法 六条边,十四种剖分方法 七条边,四十二种方法 看了好一会儿,真没发现什么规律。。。。。好吧,就这样子,很明显是符合卡特兰数规律的,看到,1,1,2,5,14就看一下是不是卡特兰数是最好不过了~~

2016年2月8日 0条评论 1点热度 阅读全文