Problem 117

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

そのままDP。

import Data.Array.IArray
measure n = mArr!n
where mArr = listArray (,n). map m $[..n]::Array Int Integer
m  = 1
m x = sum.map m'.zipWith (-) (repeat x) $ [1..4]
m' x | x <  = 
| x >=  = mArr!x
main = print.measure$ 50

というか、高々4つ前の値しか必要ないので、DPも必要ない?

ないね。

import Data.List
measure' = :::1:zipWith4 add m0 m1 m2 m3
where add a b c d = a+b+c+d
(m0:m1:m2:m3:_) = iterate tail measure'
main = print$measure'!!53
More Reading
Newer// Problem 116
Older// Problem 109