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来表示的方法总和。

Java:

public class Solution {    /**     * @param n an integer     * @return an integer     */    public int waysNCents(int n) {        int[] f = new int[n+1];        f[0] = 1;        int[] cents = new int[]{1, 5, 10, 25};        for (int i = 0; i < 4; i++)             for (int j = 1; j <= n; j++) {                if (j >= cents[i]) {                    f[j] += f[j-cents[i]];                }            }        return f[n];    }}　

Python:

class Solution:    # @param {int} n an integer    # @return {int} an integer    def waysNCents(self, n):        # Write your code here        cents = [1, 5, 10, 25]        ways = [0 for _ in xrange(n + 1)]                ways[0] = 1        for cent in cents:            for j in xrange(cent, n + 1):                ways[j] += ways[j - cent]                return ways[n]

C++:

class Solution {public:    /**     * @param n an integer     * @return an integer     */    int waysNCents(int n) {        // Write your code here        vector
     
       cents = {1, 5, 10, 25};        vector
      
        ways(n + 1);        ways[0] = 1;        for (int i = 0; i < 4; ++i)            for (int j = cents[i]; j <= n; ++j)                ways[j] += ways[j - cents[i]];        return ways[n];    }};　　　　
      
     

C++:

class Solution {public:    int makeChange(int n) {        vector
     
       denoms = {25, 10, 5, 1};        vector
      
       
         > m(n + 1, vector
        
         (denoms.size()));        return makeChange(n, denoms, 0, m);    }    int makeChange(int amount, vector
         
           denoms, int idx, vector
          
           
             > &m) { if (m[amount][idx] > 0) return m[amount][idx]; if (idx >= denoms.size() - 1) return 1; int val = denoms[idx], res = 0; for (int i = 0; i * val <= amount; ++i) { int rem = amount - i * val; res += makeChange(rem, denoms, idx + 1, m); } m[amount][idx] = res; return res; }};
           
          
         
        
       
      
     

　　

类似题目：