用记忆以最小面额进行更改

Question

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

这是详细描述的问题。这是我对递归算法的尝试：

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)访问，标准的首选库是 Data.Array。

其次，定义类型附近但以某种方式"外部"的一般方法是使用Maybe类型; 这是我为INFINITY推荐的。另外，我认为这在算法中更有意义，因为INFINITY真正的意思是"我们不能用这组面额来创造这个值"，而不是"我们可以用无限数量的硬币来创造这个值"。

所以使用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。该语法说"将函数(+1)应用于值(myArray ! (t-dval, d))的内部"，因此Just 4将成为Just 5，但Nothing将保持Nothing。