Problem 76

http://projecteuler.net/index.php?section=problems&id=76

まず再帰で書き下す。計算時間は指数時間。

count (x+1) = count' (x+1) x
count'  _ = 1
count' _ 1 = 1
count' x m | x >  =  count' (x-m) m + count' x (m-1)
| x <  = 

この再帰をDPで書き直す。計算時間はO(N^2)。

import Data.Array.IArray
cArray m = c!(m,m-1)
where c = array((,),(m,m-1)) [((n,l),count n l)|n<-[..m],l<-[1..m-1]]::Array (Int,Int) Int
count  _ = 1
count _ 1 = 1
count x m | x >= m = c!(x-m,m) + c!(x,m-1)
| x >   = c!(x,m-1)
| x <   = 
main =print.cArray$100