On Wed, Nov 14, 2012 at 07:39:33AM -0000, oleg@okmij.org wrote:
dimensional memo table. Luckily, our case is much less general. We do have a very nice dynamic programming problem. The key is the observation k' : solveR (i+1) k' After a new element, k', is produced, it is used as an argument to the solveR to produce the next element. This leads to a significant simplification:
solve2 :: String -> Array Int Int solve2 w = pI where h = length w - 1 wa = listArray (0, h) w pI = listArray (0,h) $ 0 : [ solveR i (pI!(i-1)) | i <- [1..] ] solveR :: Int -> Int -> Int solveR i k = let c = wa!i in if k > 0 && wa!k /= c then solveR i (pI!(k-1)) else let k' = if wa!k == c then k + 1 else k in k'
t2s1 = solve2 "the rain in spain" t2s2 = solve2 "aaaaaaaaaaaa" t2s3 = solve2 "abbaabba"
My hat's off to you, sir. This is kind of interesting -- I would normally consider this indexing transformation as an approach for defeating memoization, yet in this case it serves as the key that makes the broader memoization possible, lifting it up a level. Thanks! Alex P.S. A side benefit of this approach is that it's easy to switch from listArray to array, since we already have the index handy.