问题描述

Problem Description

Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.

For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, or two 5-cent coins and one 1-cent coin, or one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent.

Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 100 cents.

Input

The input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.

Output

For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.

Sample Input

11
26

Sample Output

4
13

问题分析

这道题目初学者可能比高手做得更快。

开始我还思考老半天，后来我想随便输出几个结果看看，发现速度很快。最后直接暴力通过，而且还是OMS OK。最意外的，还是选择排名还在第一位，对此我只能无语...

这里介绍一下换零钱的通用算法。将总数为amount的现金换成n种硬币的不同方式的数目等于

1. 将现金amount换成除第一种硬币之外的所有其他硬币的不同方式的数目，加上
2. 将现金数amount-value换成所有种类的硬币的不同方式的数目，其中value是第一种硬币的币值。

因为每种硬币都有换/不换两种状态。考虑其中某一种硬币，如果它不参与兑换，则兑换方式的数目就是#1；如果它参与兑换，即它的个数至少为1，排除其中一枚，那问题就缩小成现金数为amount-value，货币种类是n的子问题。

此外，题目中还有如下约束条件：

1. 如果amount=0，算1种换零钱的方式；
2. 如果amount<0，算0种；
3. 如果n=0，算0种；
4. 硬币的总数不超过100枚。

根据上面的算法和约束，容易实现一份递归的代码：

#include <stdlib.h>
#include <stdio.h>

const int coins[] = { 1, 5, 10, 25, 50 };

int count_change(int amount, int coin_kind, int deep) {
  if (deep == 0 && amount > 0) {
    return 0;
  }
  if (amount == 0) {
    return 1;
  }
  if (amount < 0 || coin_kind < 0) {
    return 0;
  }
  return count_change(amount, coin_kind - 1, deep)
       + count_change(amount - coins[coin_kind], coin_kind, deep - 1);
}

int main(void) {
  int amount;

  while (scanf("%d", &amount) != EOF) {
    printf("%d\n", count_change(amount, 4, 100));
  }

  return EXIT_SUCCESS;
}

这段代码能通过但效率不高，因为它像递归求斐波那契数一样，中间有很多冗余的计算。当然，你可以尝试去优化它，比如记住每个中间计算结果。

算法实现

前面介绍的算法和实现是通用的，即硬币的种类变化时可以很方便的适应。但针对本题可能不是最佳解法。

参考源码