题目背景

盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。

按售票处规定，每位购票者限购一张门票，且每张票售价为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的值

 

输出格式：

 

一个整数，表示方案数

 

输入输出样例

输入样例#1：

2

输出样例#1：

2 思路： 想要不尴尬就是在遇到100时，手头有50，那么，我们dp[i][j]  用i表示前i次交易，j表示手里有多少人。并dp[0][0]=1(毕竟这是一个方 案问题，你懂的) 那么，第i次的方案数一定来自i-1次。而i-1次有两种可能，1）拿50块的，2）拿100块的。 第一种情况，拿50块的，dp一定是这样的dp[i-1][j-1]后来加了一个50 第二种情况，拿100的，dp一定是dp[i-1][j+1]， 因为拿走了一个50所以在第i次后变成了dp[i][j]; 那么动态方程就出来了 if (j - 1 >= 0)　　　　//排除j==0的时候     dp[i][j] += dp[i - 1][j - 1];//50块    if (i + 1 >= j + 1)　　　　//因为总的i+1次交易不可能少于50块的个数。     dp[i][j] += dp[i - 1][j + 1];//100块 ac代码如下：

#include
       
        long long dp[100][100];int main(){    int n;    scanf("%d", &n);    dp[0][0] = 1;    for (int i = 1; i <= n+n; ++i)    {        for (int j = 0; j <= n; ++j)        {            if (j - 1 >= 0)                dp[i][j] += dp[i - 1][j - 1];//50块            if (i + 1 >= j + 1)                dp[i][j] += dp[i - 1][j + 1];//100块        }    }    printf("%lld\n", dp[n + n][0]);}