买票找零问题

问题描述：

一场激烈足球赛即将开始，售票员紧张地卖票着……。每张球票50元，现在有2n（1<=n<=18）个球迷排队购票，其中n个手持50元钞票，另外n个手持100元钞票。假设开始售票时售票处没有零钱可以找零。问这2n个人有多少种排队方式，不至使售票处出现找不出零的局面？例如当n=3时，共6人，3人持50元，3人持100元。可以找零的排队方式有如下5种：505050100100100505010010050100505010050100100501005050100100501005010050100

输入格式：

输入：输入n，表示2n个球迷，其中n个手持50元，另外n个手持100元。(n<=18)

输出格式：

输出：这2n个人可以找零的排队方式数。

分析（动态规划）：

首先，2n肯定就是偶数（这是当然啦），而且第一个必须是50元。

假设第一个50元和第K 个100元匹配（找零），第2个到第K-1个、第k+1个到第2n个也是可以实现找零的。

其中，K-1-2+1、2n-（K+1)+1也必须是偶数，即K为偶数。

假设，2n的排列个数为 f(2n) ,K=2i （ 1<= i <= n );

则排列个数 f(2n)=sum{ f(2i-2)*f(2n-2i } （ 1<= i <= n )，其中f(0)=1;

至此，递归公式就出来了。

可以看出，上面的递归计算中存在子问题的重复计算问题，这就是符合动态规划的方法了。

这里我们采用一中动态规划的变形-----备忘录方法。该方法的控制结构和递归一样（从顶向下)，区别只是在递归过程中保存每个求解过的子问题，建立备忘录以备遇到重复问题时查看，避免相同子问题的重复求解。

代码如下：

1楼abc381289080昨天 14:44

int abc (int n){ n a[0]=1; //f(0)=1 n for(int i=1;i<n;i++) n a[i]=0; //其他先置0 n return func(n); n} n应该这样吧。。

Re: wenhuayuzhihui昨天 23:46

回复abc381289080n可以，不影响结果