' 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