Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), find how many ways to represent n cents.
思路：
从最大面值的硬币开始分析，然后依次看更小面值的硬币。假设 n = 100, 所有 valid 排列组合中
num_quarters = 0 的是一类，
num_quarters = 1 的是一类，
。。。
num_quarters = 4 的是一类
num_quarters = 0 的子集中，num_dimes = 0的是一类，num_dimes = 1的是一类，。。。
按照这种思路，可以简单的用下面的代码实现：
public int makeChange(int amount) { int[] denoms = {25, 10, 5, 1}; return makeChange(amount, denoms, 0); } public int makeChange(int amount, int[] denoms, int index) { if(index == denoms.length - 1) return 1; int ways = 0; for(int i = 0; i <= amount / denoms[index]; ++i){ ways += makeChange(amount - i * denoms[index], denoms, index+1); } return ways; }
上面的代码是正确的，但是不够efficient，因为存在重复运算，比如一共有60 cents时，子集A{num_quarters=2, num_dimes=0}和子集B{num_quarters=0, num_dimes=5}是相同的，计算了两次。为了避免这种情况，下面的代码进行了优化
int makeChange(int n){ int[] denoms = {25, 10, 5, 1}; int[][] map = new int[n+1][denoms.length]; return makeChange(n, denoms, 0, map); } int makeChange(int amount, int[] denoms, int index, int[][] map){ if(map[amount][index] > 0){ return map[amount][index]; } if(index >= denoms.length - 1) return 1; int denomAmount = denoms[index]; int ways = 0; for(int i = 0; i * denomAmount <= amount; i++){ int amountRemaining = amount - i * denomAmount; ways += makeChange(amountRemaining, denoms, index +1 , map); } map[amount][index] = ways; return ways; }
原文：http://www.cnblogs.com/Antech/p/3777138.html