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.

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:
1         public static int makeChange(int           n, int denom) {
2                 int next_denom = 0;
3                 switch (denom) {
4                 case 25:
5                         next_denom = 10;
6                         break;
7                 case 10:
8                         next_denom = 5;
9                         break;
10                case 5:
11                        next_denom = 1;
12                        break;
13                case 1:
14                        return 1;
15                }
16                int ways = 0;
17                for (int i = 0; i * denom <=          n; i++) {
18                        ways += makeChange(n - i         * denom, next_denom);
19                }
20                return ways;
21        }
22           
23        System.out.writeln(makeChange(n,           25));