Problem 76
http://projecteuler.net/index.php?section=problems&id=76
まず再帰で書き下す。計算時間は指数時間。
count (x+1) = count' (x+1) x count' 0 _ = 1 count' _ 1 = 1 count' x m | x > 0 = count' (x-m) m + count' x (m-1) | x < 0 = 0
この再帰をDPで書き直す。計算時間はO(N^2)。
import Data.Array.IArray cArray m = c!(m,m-1) where c = array((0,0),(m,m-1)) [((n,l),count n l)|n<-[0..m],l<-[1..m-1]]::Array (Int,Int) Int count 0 _ = 1 count _ 1 = 1 count x m | x >= m = c!(x-m,m) + c!(x,m-1) | x > 0 = c!(x,m-1) | x < 0 = 0 main =print.cArray$100