There are four types of common coins in   US   currency:

   quarters   (25 cents)
   dimes   (10 cents)
   nickels   (5 cents),   and 
   pennies   (1 cent) 


There are six ways to make change for 15 cents:

   A dime and a nickel 
   A dime and 5 pennies
   3 nickels
   2 nickels and 5 pennies
   A nickel and 10 pennies
   15 pennies


Task

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



Optional

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



References

 an algorithm from the book Structure and Interpretation of Computer Programs.
 an article in the algorithmist.
 Change-making problem on Wikipedia.


' version 09-10-2016
' compile with: fbc -s console
 
 
Function count(S() As UInteger, n As UInteger) As ULongInt
 
  Dim As Integer i, j
  ' calculate m from array S()
  Dim As UInteger m = UBound(S) - LBound(S) +1
  Dim As ULongInt x, y
 
  '' We need n+1 rows as the table is consturcted in bottom up manner using
  '' the base case 0 value case (n = 0)
  Dim As ULongInt table(n +1, m)
 
  '' Fill the enteries for 0 value case (n = 0)
  For i = 0 To m -1
    table(0, i) = 1
  Next
 
  '' Fill rest of the table enteries in bottom up manner
  For i = 1 To n
    For j = 0 To m -1
      '' Count of solutions including S[j]
      x = IIf (i >= S(j), table(i - S(j), j), 0)
      '' Count of solutions excluding S[j]
      y = IIf (j >= 1, table(i, j -1), 0)
      ''total count
      table(i, j) = x + y
    Next
  Next
 
  Return table(n, m -1)
 
End Function
 
' ------=< MAIN >=------
 
Dim As UInteger n
Dim As UInteger value()
 
ReDim value(3)
value(0) = 1 : value(1) = 5 : value(2) = 10 : value(3) = 25
 
n = 100
print
Print " There are "; count(value(), n); " ways to make change for $";n/100;" with 4 coins"
Print
 
n = 100000
Print " There are "; count(value(), n); " ways to make change for $";n/100;" with 4 coins"
Print
 
ReDim value(5)
value(0) =  1 : value(1) =  5 : value(2) =  10
value(3) = 25 : value(4) = 50 : value(5) = 100
 
n = 100000
Print " There are "; count(value(), n); " ways to make change for $";n/100;" with 6 coins"
Print
 
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End