Problem Statement

There are four types of common coins in   US   currency:

There are six ways to make change for 15 cents:

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

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

Let's start with the solution:

let changes amount coins =
  let ways = Array.make (amount + 1) 0L in
  ways.(0) <- 1L;
  List.iter (fun coin ->
    for j = coin to amount do
      ways.(j) <- Int64.add ways.(j) ways.(j - coin)
    done
  ) coins;
  ways.(amount)

let () =
  Printf.printf "%Ld\n" (changes    1_00 [25; 10; 5; 1]);
  Printf.printf "%Ld\n" (changes 1000_00 [100; 50; 25; 10; 5; 1]);
;;