Coins

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.

 /**  
  * numberOfWays(25, 3) = numberOfWays(25-1, 0) + numberOfWays(25-5, 1)  
  * + numberOfWays (25-10, 2) + numberOfWays (25-25, 3)  
  *   
  * numberOfWays(25-1, 0) = 1  
  * numberOfWays(25-5, 1) = numberOfWays(20, 1) = numberOfWays(20-1, 0)   
  * + numberOfWays(20-5, 1)   
  * ......   
  * @author zsunm  
  *  
  */  
 public class Coin {  
        
      private static final int[] COINS = {1, 5, 10, 25};  
        
      public static int numberOfWays(int n){  
           if (n == 0) return 0;  
           return numberOfWays(n, 3);  
      }  
        
      /**  
       * The number of ways to represent n cents by using the coins  
       * up to the specified coinIndex of the COINS array  
       * Example 1: numberOfWays(10, 2) means the number of ways  
       * to represent 10 cents using 1 cent, 5 cents, and 10 cents,   
       * because COINTS[2] = 10  
       *   
       * Example 2: numberOfWays(25, 3) means the number of ways  
       * to represent 25 cents using 1 cent, 5 cents, 10 cents, and 25 cents   
       * because COINTS[3] = 25  
       *   
       * @param n cents  
       * @param coinIndex the coin index of COINS array that can be used up to  
       * @return  
       */  
      private static int numberOfWays(int n, int coinIndex) {  
           if (n < 0){  
                return 0;  
           }  
           if (n == 0){  
                return 1;  
           }  
           int result = 0;  
           for (int i=0; i<=coinIndex; i++){  
                result += numberOfWays(n-COINS[i], i);  
           }  
           return result;  
      }  
   
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           System.out.println(numberOfWays(25));  
      }  
   
 }