exchanges.hs

import Data.Array
import Data.Array.ST
import Control.Monad (forM_, liftM2)

main = print $ exchanges coins 10000 ! 10000
  where
    coins = [1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000]

exchanges :: (Ix a, Enum a, Num a, Num e) => [a] -> a -> Array a e
exchanges cs n = runSTArray $ do
  a <- newArray (0,n) 0
  writeArray a 0 1
  forM_ cs $ \c ->
    forM_ [c .. n] $ \i ->
      liftM2 (+) (readArray a (i-c)) (readArray a i) >>= writeArray a i
  return a