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.


import BigInt
 
func countCoins(amountCents cents: Int, coins: [Int]) -> BigInt {
  let cycle = coins.filter({ $0 <= cents }).map({ $0 + 1 }).max()! * coins.count
  var table = [BigInt](repeating: 0, count: cycle)
 
  for x in 0..<coins.count {
    table[x] = 1
  }
 
  var pos = coins.count
 
  for s in 1..<cents+1 {
    for i in 0..<coins.count {
      if i == 0 && pos >= cycle {
        pos = 0
      }
 
      if coins[i] <= s {
        let q = pos - coins[i] * coins.count
        table[pos] = q >= 0 ? table[q] : table[q + cycle]
      }
 
      if i != 0 {
        table[pos] += table[pos - 1]
      }
 
      pos += 1
    }
  }
 
  return table[pos - 1]
}
 
let usCoins = [100, 50, 25, 10, 5, 1]
let euCoins = [200, 100, 50, 20, 10, 5, 2, 1]
 
for set in [usCoins, euCoins] {
  print(countCoins(amountCents: 100, coins: Array(set.dropFirst(2))))
  print(countCoins(amountCents: 100000, coins: set))
  print(countCoins(amountCents: 1000000, coins: set))
  print(countCoins(amountCents: 10000000, coins: set))
  print()
}