卡特兰数

一道经典卡特兰数列题

P1044 [NOIP2003 普及组] 栈

卡特兰数列原理:

令h(1)＝1，catalan 数满足递归式：

h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2)

该递推关系的解为：h(n)=c(2n-2,n-1)/n (n=1,2,3,...)

具体的证明过程较为繁琐

洛谷《深入浅出程序设计竞赛》（基础篇）中递推章节利用了求出栈序列的总数量这一问题来进行证明

此题题解也有大佬说明

因此得出,栈的出栈序列数量与n的关系符合卡特兰数列

可以得出代码

#include
using namespace std;
int n,f[20];
int main()
{
	f[0]=f[1]=1;
	cin >> n;
	for(int i=2;i<=n;i++)
		for(int j=0;j<=i;j++)
			f[i]+=f[j]*f[i-j-1];
	cout << f[n] << endl;
	return 0;
}

此题也能用记搜,dp写法,这里不再描述