Haskell：如何记住这个算法？

Question

我在 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))

然而，它在一些较大的测试用例上超时。我看到了这篇关于使用let绑定实现记忆的文章，但它大部分都让我无法理解，我不确定我将如何在这里实现它。有什么帮助吗？

我重写了它并获得了实质性的性能改进，但我仍然在黑客排名练习中超时：

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组硬币进行总和的方法总数，并且您获得了一个新的不同价值硬币x，您可以使用以下事实将列表更新a为新列表b：

• 第一个x元素不会改变；因为，您不能以低于 的金额使用新硬币x。所以，take x a。

• 对于其余元素：

  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

就像问题中的例子一样。