马戏团【动态规划】

马戏团【动态规划】

#include <iostream>
#include <cstring>
using namespace std;int dp[21][21];
int fun(int n,int k){	//k表示余额份数if(dp[n][k]>=0)return dp[n][k];int ans;if(k<0||k>n)		//当余额小于0，或者余额超过n份ans = 0;else if(n==0)		//当递归到最后一个人，且上一步已经判断过最后一人是否合法ans = 1;elseans = fun(n-1,k-1)+fun(n-1,k+1);	//中间的时候，返回加入一个5元人(k+1)或加入一个10元人(k-1)。dp[n][k]=ans;return ans;
}
int main(){int n;while(scanf("%d",&n)!=EOF){memset(dp,-1,sizeof dp);cout<<fun(2*n,0)<<endl;}return 0;
}