用动态规划求解爆破气球问题

Question

继续我不再使用之前来解决所述 这里问题的地方，我现在使用动态编程( dynamic，以下是DP上的Tikhon Jelvis博客)解决了同样的问题。

要更新，挑战是找到一个顺序来爆裂一排气球，这些气球将获得最多的硬币。每次气球爆发时，我们都会获得\$C_{i-1} \cdot C_i \cdot C_{i+1}$硬币，然后气球I-1和\$i+1\$彼此相邻。

import qualified Data.Array as Array


burstDP :: [Int] -> Int
burstDP l = go 1 len
  where
    go left right | left <= right = maximum [ds Array.! (left, k-1)
                                            + ds Array.! (k+1, right)
                                            + b (left-1)*b k*b (right+1) | k <- [left..right]]
                  | otherwise    = 0
    len = length l
    ds = Array.listArray bounds
           [go m n | (m, n) <- Array.range bounds]
    bounds = ((0,0), (len+1, len+1))
    l' = Array.listArray (0, len-1) l
    b i = if i == 0 || i == len+1 then 1 else l' Array.! (i-1)

我在找：

1. 正确性
2. 程序结构
3. 习语Haskell
4. 任何其他可以使用的高阶函数
5. 其他可以完成的优化

Answer 1

您使用Array进行回忆录可以提取到array-memoize中。

如果一个人可以停止，而不是有负气球下降的分数，go可以浓缩成一个情况。

import Data.Function.ArrayMemoize (arrayMemoFix)
import Data.Array ((!), listArray)

burstDP :: [Int] -> Int
burstDP l = arrayMemoFix ((0,0), (len+1, len+1)) go (1, len) where
  go ds (left, right) = maximum $ 0 :
    [ds (left, k-1) + ds (k+1, right) + b (left-1)*b k*b (right+1) | k <- [left..right]]
  b = (!) $ listArray (0, len+1) (1 : l ++ [1])
  len = length l

如果您不太关心性能，我们也可以直接在气球列表上使用memoize：

burstDP :: [Int] -> Int
burstDP = memoFix3 go 1 1 where go ds l r b = maximum
  [ ds left l x + ds right x r + l*x*r
  | (left, x:right) <- zip (inits b) (tails b)
  ]