题目背景
盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。
按售票处规定，每位购票者限购一张门票，且每张票售价为50元。在排成长龙的球迷中有N个人手持面值50元的钱币，另有N个人手持面值100元的钱币。假设售票处在开始售票时没有零钱。试问这2N个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。
题目描述
例如当n=2是，用A表示手持50元面值的球迷，用B表示手持100元钱的球迷。则最多可以得到以下两组不同的排队方式，使售票员不至于找不出钱。
第一种:A A B B
第二种:A B A B
[编程任务]
对于给定的n (0≤n≤20),计算2N个球迷有多少种排队方式，可以使售票处不至于找不出钱。
输入输出格式
输入格式：
一个整数，代表N的值
输出格式：
一个整数，表示方案数
输入输出样例
说明
必开QWORD
测试：N=15
回溯:1秒（超时）
模拟栈：大于10分钟
递归算法：1秒（超时）
动态规划：0 MS
组合算法：16 MS
思路：
一：卡特兰数
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; long long f[10000]; int main(){ scanf("%d",&n); f[0]=f[1]=1; 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]; }
二：动态规划。f[i][j]表示已经收了i个人的钱，现在手里有j张50的。
那 当现在收的人的钱是50元时 f[i][j]+=f[i-1][j-1]。因为多一张50的，所以现在50元比起原来就多了一张。
当现在收的人的钱是100元时 f[i][j]+=f[i-1][j+1]。因为要找一张50的，所以比起原来就少了一张50的。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; int f[42][42]; int main(){ scanf("%d",&n); f[0][0]=1; for(int i=1;i<=2*n;i++) for(int j=0;j<=min(i,n);j++){ if(j-1>=0) f[i][j]+=f[i-1][j-1]; if(j<=i) f[i][j]+=f[i-1][j+1]; } cout<<f[2*n][0]; }