p1044栈,卡特兰数

设f【i】表示i个数的方法数
最后出来的数是i的方法数f【i-1】*f【n-i】,(这里i-1+n-i=n-1就可以大致判断出事卡特兰数)
有n个数的方法数等于每个数最后出来的方法数的和
即:,第一个数是0
一个数最后出来的方法数是1——f【0】=1
二个数最后出来的方法数是1——f【1】=2
用卡特兰数推导公式,只用上一层的除法
#include<bits/stdc++.h>
using namespace std;

long long n,f[20];
int main(){
	cin>>n;
	f[1]=1;
	for(int i=2;i<=n;i++) f[i]=f[i-1]*(4*i-2)/(i+1);
	cout<<f[n];
	return 0;
} 



全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 11:47
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务