[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.

这道题给定一个钱数，让我们求用quarter，dime，nickle和penny来表示的方法总和，很明显还是要用递归来做。比如我们有50美分，那么
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) =
　　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)

而这里面的每项又可以继续往下拆成nickle和penny，整体是一个树形结构，计算顺序是从最底层开始，也就是给定的钱数都是由penny组成的情况慢慢往回递归，加一个nickle，加两个nickle，再到加dime和quarter

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);
}
Read full article from [CareerCup] 9.8 Represent N Cents 美分的组成 - Grandyang - 博客园