Tammy wants to get change for 30c. The only coins she can get are quarters, nickels and dimes. How many different ways can she get 30c using only these coins?
it should not be too hard to actually list them
Q-D-N
0 0 6
0 1 4
0 2 2
0 3 0
1 0 5
To find the number of different ways Tammy can get 30 cents using quarters, nickels, and dimes, we can approach the problem using a dynamic programming technique called coin change.
First, let's define a function, `countWays(n)`, that takes an amount `n` as input and returns the number of ways Tammy can make change for `n` cents. To find `countWays(30)`, we'll recursively calculate it as follows:
1. Base case: If `n` is 0 (which means the remaining change needed is 0), there is exactly one way to make change (by using no coins). So, `countWays(0) = 1`.
2. If `n` is negative (which means Tammy has overpaid), there are no valid ways to make change. So, `countWays(n) = 0` for `n < 0`.
3. If `n` is positive, we consider the coins one by one:
a. When considering the quarter (25 cents), Tammy has two choices: she can either include it in the current combination or exclude it. If she includes the quarter, the remaining amount of change needed is reduced by 25 cents, and we need to find the number of ways to make change for the reduced amount. If she excludes the quarter, the problem remains the same. So, the number of ways Tammy can make change for `n` cents using quarters is `countWays(n - 25)`.
b. Similarly, if Tammy includes a dime (10 cents), the number of ways to make change is `countWays(n - 10)`.
c. And if Tammy includes a nickel (5 cents), the number of ways is `countWays(n - 5)`.
4. Finally, we return the sum of the three different ways calculated in the previous steps: `countWays(n) = countWays(n - 25) + countWays(n - 10) + countWays(n - 5)`.
To find the total number of ways Tammy can make 30 cents change using quarters, nickels, and dimes, we simply need to calculate `countWays(30)`.