How to find a recurrence relation for F(n) the number of ways to make n cents change using only pennies, nickels(5cents), and dimes(10cents)... So for 9 cents, there are 6 ways, which are
1 1 1 1 1 1 1 1 1 ( 9 pennies) 5 1 1 1 1 (1 nickel followed by 4 pennies) 1 5 1 1 1 1 1 5 1 1 1 1 1 5 1 1 1 1 1 5
My attempt so far:
I tried cases up to n=9 just to see how the numbers change
n=0: 1 way (0,0,0) where each element in this vector represent number of penny, nickel and dime respectively n=1 1 * (1,0,0) 1 way n=2 1 * (2,0,0) 1 way n=3 1 * (3,0,0) 1 way n=4 1 * (4,0,0) 1 way n=5 1 * (5,0,0) 1 * (0,1,0) 2 ways n=6 1 * (6,0,0) 2 * (1,1,0) 3 ways n=7 1 * (7,0,0) 3 * (2,1,0) 4 ways n=8 1 * (8,0,0) 4 * (3,1,0) 5 ways n=9 1 * (9,0,0) 5 * (4,1,0) 6 ways
But I still can't seem to find any sort of subroutine which I can use to build my recurrence.