P1044

卡特兰数经典例题

原题链接：栈

解决方法： Catalan Number

为何是卡特兰数？解释原理：

x为最后一个出栈的，可以将原来的栈分为两部分

• 小于x(x-1个)

• 大于x(n-x个)

排列后可得x的取值为catalan[x]=catalan[x-1]*catalan[n-x]

直接动归 可得 ans=catalan[0]*catalan[n-1]+catalan[1]catalan[n-2]+…+catalan[n-1]*catalan[0]

上述语句即为卡特兰数的公式

参见百度百科

//P1044     Stack
//SOLUTION: Catalan Number
#include<bits/stdc++.h>
using namespace std;

int n,ans;
long long catalan[50];

int main()
{
	catalan[0]=1;catalan[1]=1;catalan[2]=2;//定义卡特兰数前几个数的值
	cin>>n;
	for(int i=3;i<=n;i++)
	{
		for(int j=0;j<=n-1;j++)
		{
			catalan[i]+=catalan[j]*catalan[i-j-1];//计算需要的卡特兰数
		}
	}
	cout<<catalan[n];//输出答案
	return 0;
}

本片题解基于 @inexistent改编