买票找零问题
问题描述：
一场激烈足球赛即将开始，售票员紧张地卖票着……。每张球票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;
至此，递归公式就出来了。
可以看出，上面的递归计算中存在子问题的重复计算问题，这就是符合动态规划的方法了。
这里我们采用一中动态规划的变形-----备忘录方法。该方法的控制结构和递归一样（从顶向下)，区别只是在递归过程中保存每个求解过的子问题，建立备忘录以备遇到重复问题时查看，避免相同子问题的重复求解。
代码如下：
