algorithm - Haskell:如何内存这个算法？

Question

我把这个解决方案写到 coin change problem on HackerRank :

makeChange :: Int -> [Int] -> Int
makeChange n ys = go n (sort ys)
    where go _ [] = 0
          go n (x:xs)
            | x == n = 1
            | x > n = 0
            | otherwise = (makeChange n xs) + (makeChange (n - x) (x:xs))

但是它会在一些较大的测试用例上超时。我看到了this关于使用 let 绑定(bind)实现记忆化的文章，但它主要让我头疼，我不确定我将如何在这里实现它。有帮助吗？

我重写了它并获得了显着的性能改进，但我仍然在黑客排名练习上超时:

makeChange' :: Int -> [Int] -> Int
makeChange' =
    let go _ [] = 0
        go n (x:xs)
          | x == n = 1
          | x > n = 0
          | otherwise = (makeChange' n xs) + (makeChange' (n - x) (x:xs))
    in go

f (x:y:xs) = makeChange' x ys
    where ys = sort xs
main = interact $ show . f . map read . words

我将预排序移到了一个中间函数 f 中，我也用它来处理来自 Hacker Rank 的输入。他们给你一个字符串，其中包含更改目标、更改数组的长度和更改单元数组。我使用 f 从输入中删除长度。

Answer 1

这个问题不需要需要内存。如果a 是一个无限长度 列表，其中a !! n 是总计 n 总和的方法的总数，你得到一个新的值(value) x 的独特硬币，你可以使用以下事实将列表 a 更新为新列表 b:

• 前x元素不会改变；因为，您不能将新硬币用于小于 x 的金额。所以，取 xa。

• 对于剩余的元素:

  b(n) = a(n) + b(n - x)
  

  第一个加数表示根本不使用新硬币，第二个加数表示至少使用一次。

这可以简单地使用右折来实现，初始值为 [1, 0, 0, ...]，因为没有硬币，您可能赚到的唯一总和为零。 Haskell 惰性在这里也非常有用:

solve :: Int -> [Int] -> Int
solve n xs = (foldr go (1:repeat 0) xs) !! n
  where go x a = let b = (take x a) ++ zipWith (+) b (drop x a) in b

然后:

\> solve 4 [1, 2, 3]
4
\> solve 10 [2, 5, 3, 6]
5

如问题中的示例。