In England the currency is made up of pound, ￡, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) and ￡2 (200p).

It is possible to make ￡2 in the following way:

1￡1 + 150p + 220p + 15p + 12p + 31p

How many different ways can ￡2 be made using any number of coins?

動的計画法。memoiseの出番です。

とおもったら、条件を満たすうち最適なものを求めないさではなく

条件を満たすのは何通り

という問題だった。これは再帰でかけるぞ。こんなことしなくてももっと簡単に。 

import Control.Monad.State
import Control.Monad
import Prelude hiding(lookup)
import Data.Map (Map,lookup,insert,empty)
import Data.Maybe
type Table k v = Map k v
type Memo a b = State (Table a b) b
memoise :: Ord a => (a -> Memo a b) -> a -> Memo a b
memoise f x = do
table <- get
case (lookup x table) of
Just y -> return y
Nothing -> do fx <- f x
table' <- get
put(insert x fx table')
return fx
runM :: (a -> Memo a b) -> a -> b
runM m v = evalState (m v) empty
coins = [200,100,50,20,10,5,2,1]::[Int]
coin :: ([Int],Int)->Memo ([Int],Int) (Maybe Int)
coin ([],_) = return Nothing
coin (c:cs,v) | v <  = return Nothing
| v ==  =return$Just 1
| v >  = memoise coin' (c:cs,v)
where coin' (c:cs,v)= do
p1 <-  coin (c:cs,v-c)
p2 <-  coin (cs,v)
return.listToMaybe.scanr1 (+).catMaybes$ [p1,p2]

シンプル、だが上のほうが断然速い。さすが動的計画法 

count _  = 1
count [] _ = 1
count (c:cs) v =sum$map(count cs)[v-n|n<-[,c..v]]
main =print$ count [200,100,50,20,10,5,2] 200