Question9_8.java

/**
 * 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
 *  
 * Time  Complexity: O(n)
 * Space Complexity: O(n)
 */

public class Question9_8 {
    public int getNumberOfWays(int n, int[] candidates) {
        if (candidates == null || candidates.length == 0) {
            return 0;
        }
        
        int[][] numberOfWays = new int[n + 1][candidates.length];
        recGetNumberOfWays(n, candidates, 0, numberOfWays);
        
        return numberOfWays[n][0];
    }
    
    
    private int recGetNumberOfWays(int n, int[] candidates, int index, int[][] numberOfWays) {
        if (index >= candidates.length - 1) {
            return 1;
        }
        
        if (numberOfWays[n][index] != 0) {
            return numberOfWays[n][index];
        }

        
        int ways = 0;
        int centValue = candidates[index];
        for (int i = 0; i * centValue <= n; ++i) {
            ways += recGetNumberOfWays(n - i * centValue, candidates, index + 1, numberOfWays);
        }
        
        numberOfWays[n][index] = ways;
        
        return ways;
    }

    
    
    public static void main(String[] args) {
        Question9_8 question9_8 = new Question9_8();
        int[] candidates = new int[] {25, 10, 5, 1};
        for (int n = 0; n <= 100; ++n) {
            System.out.println("makeChange(" + n + ") = " + question9_8.getNumberOfWays(n, candidates));
        }
    }
}