**Problem**

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

**Method 1 - Recursion**

This is a recursive problem, so let’s figure out how to do makeChange(n) using prior solutions (i.e., sub-problems).

Let’s say n = 100, so we want to compute the number of ways of making change of 100 cents. What’s the relationship to its sub-problems?

We know that makeChange(100):

= makeChange(100 using 0 quarters) + makeChange(100 using 1 quarter) + makeChange(100 using 2 quarter) + makeChange(100 using 3 quarter) + makeChange(100 using 4 quarter)

Can we reduce this further? Yes!

= makeChange(100 using 0 quarters) + makeChange(75 using 0 quarter) + makeChange(50 using 0 quarters) + makeChange(25 using 0 quarters) + 1

Now what? We’ve used up all our quarters, so now we can start applying our next biggest denomination: dimes.

This leads to a recursive algorithm that looks like this:

public static int makeChange(int n, int denom) { int next_denom = 0; switch (denom) { case 25: next_denom = 10; break; case 10: next_denom = 5; break; case 5: next_denom = 1; break; case 1: return 1; } int ways = 0; for (int i = 0; i * denom <= n; i++) { ways += makeChange(n - i * denom, next_denom); } return ways; }

**References**

http://tianrunhe.wordpress.com/2012/03/27/number-of-ways-of-representing-n-cents-using-quarters-dimes-nickels-and-pennies/

## 0 comments:

## Post a Comment