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