Problem Statement

There are four types of common coins in   US   currency:

There are six ways to make change for 15 cents:

How many ways are there to make change for a dollar using these common coins?     (1 dollar = 100 cents).

Less common are dollar coins (100 cents);   and very rare are half dollars (50 cents).   With the addition of these two coins, how many ways are there to make change for $1000? (Note:   the answer is larger than   232).

Let's start with the solution: