Haskell Dynamic Programming

haskell_dp.hs

-- Recursive and Dynamic Programming solutions to the recurrence N(k) = 2N(k - 3) + N(k - 2) 
compute_rec :: Int -> Int
compute_rec 0 = 0
compute_rec 1 = 0
compute_rec 2 = 2
compute_rec k = 2 * (compute_rec (k - 3)) + (compute_rec (k - 2))

compute :: Int -> Int
compute k = cache !! k
    where
        cache = [0, 0, 2] ++ [2 * (cache !! (k - 3)) + (cache !! (k - 2)) | k <- [3..]]