通过记忆化以最小面额进行找零

Question

我想知道如何使用记忆来制作高效的算法。特别是，有没有办法使 Haskell 中索引值的访问时间为 O(1)？

这里是the problem described in detail。这是我对递归算法的尝试：

denom :: (Int, Int) -> [Int] -> Int
denom (_, 0) _ = 0
denom (0, _) _ = (maxBound :: Int) - 1000 -- subtracting 1000 otherwise overflows
denom (i, j) di
  | v > j = denom (i-1, j) di
  | otherwise = min (denom (i-1, j) di) (1 + denom (i, j-v) di)
  where v = di !! (i - 1)

此外，我如何在 Haskell 中声明 INFINITY 以便 min 在所有情况下都有效？

Answer 1

首先，要在 Haskell 中进行 O(1) 访问，标准 go-to 库是 Data.Array.

其次，定义接近类型但不知何故 "outside" 的东西的一般方法是使用 Maybe 类型；这是我为 INFINITY 推荐的。另外，我认为这在算法中更有意义，因为 INFINITY 真正意味着 "we can't make this value with this set of denominations"，而不是 "we can make this value with an infinite number of coins".

所以使用 Maybe，我们首先要定义的是适用于 Maybe Int 的 min 版本：

myMin :: Ord a => Maybe a -> Maybe a -> Maybe a
myMin (Just a) (Just b) = Just $ min a b
myMin Nothing x = x
myMin x Nothing = x

然后，我们可以使用链接页面中给出的算法来解决这个问题：

minCoinCoint :: Int -> [Int] -> Maybe Int
minCoinCoint target denoms = res (target, length denoms)
  where
    denomArray = listArray (0, length denoms) (0:denoms)
    myArrayBounds = ((0, 0), (target, length denoms))
    myArray = array myArrayBounds [(i, res i) | i <- range myArrayBounds]
    res (_, 0) = Nothing
    res (0, _) = Just 0
    res (t, d) = let dval = denomArray ! d
                     prev1 = myArray ! (t, d-1)
                     prev2 = if t >= dval
                             then (+1) <$> (myArray ! (t-dval, d))
                             else Nothing
                 in myMin prev1 prev2

就是这样。（嗯，假设你还记得文件顶部的 import Data.Array 行）

请注意，myArray 是通过引用 res 构建的，res 通过在 myArray.

中查找值来进行所有递归调用

这个语法可能有点混乱：

(+1) <$> (myArray ! (t-dval, d))

之所以这样做，是因为请记住 myArray 的每个元素都不是 Int，而是 Maybe Int。该语法表示 "apply the function (+1) to the inside of the value (myArray ! (t-dval, d))"，因此 Just 4 将变为 Just 5，但 Nothing 仍将是 Nothing。

通过记忆化以最小面额进行找零

Making change with minimum denominations with memoization

haskell

memoization

dynamic-programming