Coin Change [Haskell]

Readme.md

the coin change problem implemented in Haskell.

• Problem explain: https://www.youtube.com/watch?v=GafjS0FfAC0
• Haskell memoization: http://www.haskell.org/haskellwiki/Memoization
• Same problem in C++: http://avdongre.wordpress.com/2011/06/21/coin-change-problem-c-solution/
• Memory problem! compile with "-O2"

CoinChange.hs

import Data.List (foldl1')
import Data.Array

change:: [Int] -> Int -> Int
change cs v = change' v
  where
    memo = array (0, v) [(x, change'' x) | x <- [0..v]]
    change' v = memo ! v
    change'' 0 = 0
    change'' v = foldl1' min [change' $! (v-i) | i <- takeWhile (<=v) cs] +1


main = do
  print $ change [1..4] 100000