dynamic programming in haskell

sol01.hs

import qualified Data.MemoCombinators as Memo

coins = [1,2,5,10,20,50,100,200]

sol1 = f
    where f :: Int -> Int -> Int
          f = Memo.memo2 Memo.integral (Memo.arrayRange (0,7)) mf
            where mf :: Int -> Int -> Int
                  mf n k | (k >= 8) || (n < 0) = 0
                         | n == 0 = 1
                         | otherwise = (f n (k+1)) + (f (n - coins !! k) k)

main = do
    print $ sol1 200 0

sol02.hs

coins = [1,2,5,10,20,50,100,200]

sol2 = mf
    where memo :: (Num a, Enum a) => (a -> b) -> [b]
          memo f = map f (enumFrom 0)
          mf :: Int -> Int -> Int
          mf = \n k -> fvalue !! n !! k
          fvalue = fmap memo (memo f)
          f :: Int -> Int -> Int
          f n k | (k >= 8) || (n < 0) = 0
                | n == 0 = 1
                | otherwise = (if k < 7 then mf n (k+1) else 0) + (if n - coins!!k >= 0 then mf (n - coins !! k) k else 0)

main = do
    print $ sol2 200 0

sol03.hs

coins = [1,2,5,10,20,50,100,200]

sol3 = (!!) (ways [1,2,5,10,20,50,100,200])
    where ways [] = 1 : repeat 0
          ways (coin:coins) = n
              where n = zipWith (+) (ways coins) (replicate coin 0 ++ n)

main = do
    print $ sol3 200

sol04.hs

import qualified Data.MemoTrie as MT

coins = [1,2,5,10,20,50,100,200]

sol4 = f
    where f :: Int -> Int -> Int
          f = MT.memo2 mf
            where mf :: Int -> Int -> Int
                  mf n k | (k >= 8) || (n < 0) = 0
                         | n == 0 = 1
                         | otherwise = (f n (k+1)) + (f (n - coins !! k) k)

main = do
    print $ sol4 200 0

sol05.hs

import Data.Maybe
import qualified Data.Map as M


coins = [1,2,5,10,20,50,100,200]

sol5 = mf
    where memo :: (Num a, Enum a) => (a -> b) -> [b]
          memo f = map f (enumFrom 0)
          gwvals = fmap memo (memo f)
          gwByMap :: Int -> Int -> Int -> Int -> Int
          gwByMap maxX maxY = \x y ->  fromMaybe (f x y) $ M.lookup (x,y) memomap
            where memomap = M.fromList $ concat [[((x',y'), z) | (y',z) <- zip [0..maxY] ys] | (x',ys) <- zip [0..maxX] gwvals]
          mf :: Int -> Int -> Int
          mf = gwByMap 205 8
          f :: Int -> Int -> Int
          f n k | (k >= 8) || (n < 0) = 0
                | n == 0 = 1
                | otherwise = (if k < 7 then mf n (k+1) else 0) + (if n - coins!!k >= 0 then mf (n - coins !! k) k else 0)

main = do
    print $ sol5 200 0

sol06.hs

import Data.Array.IArray

coins = [1,2,5,10,20,50,100,200]

sol6 = ans
    where ans :: Int -> Int -> Int
          ans n k = table ! (n, k)
            where table :: Array (Int, Int) Int
                  table = listArray ((0,0), (300,7)) [f i j | i <- [0..n], j <- [0..7]]
                  f n k | (k >= 8) || (n < 0) = 0
                        | n == 0 = 1
                        | otherwise = (if k < 7 then table ! (n, (k+1)) else 0) + (if (n - coins!!k) >= 0 then table ! ((n - coins !! k), k) else 0)

main = do
    print $ sol6 200 0