1、卡诺兰概念：

卡诺兰数列的递推关系：h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2),这是n阶递推关系;

数列的通项：F(n)=C(2n,n)/(n+1)

2、可以解决的问题：

参考链接：

1、n个元素的二叉查找树有多少种。

2、n*n棋盘从左下角走到右上角而不穿过主对角线的走法。

3、2n个人排队买票问题，票价50，n个人拿50元，n个人拿100元，售票处无零钱，能顺利卖票的所有排队方式。

4、n个元素全部入栈并且全部出栈的所有可能顺序。

5、矩阵链所有乘法顺序问题（同问题1）。

6、凸多边形剖分成三角形的方法数（同问题1）。

 

 

3、答案：

这些问题的答案都是卡特兰数F(n)。但是很明显可以看出后三个问题是同质的。

都可以抽象成2n个操作组成的操作链，其中A操作和B操作各n个，且要求截断到操作链的任何位置都有：A操作（向右走一步、收到50元、元素入栈）的个数不少于B操作（向上走一步、收到100元找出50元、元素出栈）的个数。故问题2、3、4其实是同一个问题。

前几项为1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796。

4、算法：

#采用卡诺兰数通解来求解        if n<=1:            return 1        elif n>=2:            m=reduce(lambda x,y:x*y,[i for i in range(n+2,2*n+1)])            n=reduce(lambda x,y:x*y,[j for j in range(1,n+1)])            return m/n        #采用数列递推关系来求解,递归求解，超出时间限制        if n<=1:            return 1        res=0        for i in range(1,n+1):            res+=self.numTrees(i-1)*self.numTrees(n-i)        return res        #采用数列递推关系来求解，循环求解        if n<=1:            return 1        res=[1]*(n+1)        for i in range(2,n+1):            count=0            for j in range(0,i):                count+=res[j]*res[i-j-1]            res[i]=count        return res[n]