７６問目
http://projecteuler.net/index.php?section=problems&id=76
100 を 2 個以上に分割する方法は何通りあるか。
「2 個以上に分割」≡「99 以下の数で分割」です。
100 というそれほど大きくない数が相手なので、ここは List にメモして凌いでます。
main = print $ part 100 99 parts :: [[Int]] parts = [ [ count m n | n <- [0..] ] | m <- [0..] ] part :: Int -> Int -> Int part _ 0 = 1 part _ 1 = 1 part m n | (m < n) = parts !! m !! m | otherwise = sum [ parts !! (m-n') !! n' | n' <- [1..n] ]
