## Saturday, July 2, 2016

### [CareerCup] 9.8 Represent N Cents 美分的组成 - Grandyang - 博客园

https://xizha677.gitbooks.io/codenotes/content/number-of-ways-to-represent-n-cents.html
http://www.jiuzhang.com/solutions/number-of-ways-to-represent-n-cents/
Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.
Example:
n = 11
``````11 = 1 + 1 + 1... + 1
= 1 + 1 + 1 + 1 + 1 + 1 + 5
= 1 + 5 + 5
= 1 + 10
``````
``` We first find the number of ways by using 1 cent, then we add the number of ways by using 5 cents onto that. We repeat this process for each kind of coins. public int waysNCents(int n) { int[] coins = new int[] {1, 5, 10, 25}; int[] f = new int[n + 1]; f[0] = 1; for (int i = 0; i < coins.length; i++) { for (int j = 1; j <= n; j++) { if (j >= coins[i]) { f[j] = f[j] + f[j - coins[i]]; } } } return f[n]; } ```
[CareerCup] 9.8 Represent N Cents 美分的组成 - Grandyang - 博客园
9.8 Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

makeChange(50) =
makeChange(50 using 0 quarter) +
makeChange(50 using 1 quarter) +
makeChange(50 using 2 quarters)

makeChange(50 using 0 quarter) =
makeChange(50 using 0 quarter， 0 dimes) +
makeChange(50 using 0 quarter， 1 dimes) +
makeChange(50 using 0 quarter， 2 dimes) +
makeChange(50 using 0 quarter， 3 dimes) +
makeChange(50 using 0 quarter， 4 dimes) +
makeChange(50 using 0 quarter， 5 dimes)

X.  Alternatively, we could use an actual hash table that maps from amount to a new hash table, which then maps from denom to the precomputed value.
int makeChange(int n) {
int[] denoms = {25, 10, 5, l};
int[][] map = new int[n + l][denoms.length]; // prec omputed vals
return makeChange(n, denoms, 0, map);
}

int makeChange(int amount, int[] denoms, int index, int[][] map) {
if (map[amount][index] > 0) {//retrieve value
return map[amount][index];
}
if (index >= denoms.length - 1) return 1; // one denom remaining
int denomAmount denoms[index];
int ways = 0;
for (int i= 0; i * denomAmount <= amount; i++) {
//go to next denom, assuming i coins of denomAmount
int amountRemaining = amount - i * denomAmount;
ways += makeChange(amountRemaining, denoms, index + 1, map);
}
map[amount][index] = ways;
return ways;
}

int makeChange(int amount, int[] denoms, int index) {
if (index >= denoms.length - 1) return 1; // last denom
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);
}
return ways;
}
int makeChange(int n) {
int[] denoms = {25, 10, 5, 1};
return makeChange(n, denoms, 0);
}