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 绑定实现记忆化的文章，但它大部分都让我头疼，我不确定我将如何在这里实现它。有帮助吗？

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

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

我认为最好使用显式二维数组来解决这个问题。实际上，我们为每个函数调用的结果提供了该数组中的一个位置。这使我们最多只需要评估一次功能。我们必须添加更多的样板文件，因为我们需要检查我们是否在数组外索引

makeChange :: Int -> [Int] -> Int
makeChange n ys = arr ! (n,1)
    where 
      len = length xs
      xs = sort ys
      arr = array ((1,1),(n,len)) [((i,j), go i j x)| i <- [1..n], (j,x) <- zip [1..] xs]
      go n ix x | x == n = 1
                | x > n = 0
                | otherwise = (if ix + 1 <= len then (arr ! (n, ix+1)) else 0) + 
                              (if (n-x) > 0 then (arr ! ((n-x), ix)) else 0)

Answer 2

这个问题不需要记忆。如果 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

如问题中的示例。

Answer 3

我将尝试演示 behzad.nouri 的代码是如何工作的，以便我自己理解它：

牢记 Haskell 的惰性，我们观察到 !! n 意味着我们的最终列表将被评估到它的第 (n+1) 个元素。我们每个硬币的主要区块是：

let b = (take x a) ++ zipWith (+) b (drop x a) in b

这里有一个小技巧，因为 b 是一个列表。请注意，如果 b 是整数，则类似的自引用将不起作用。假设我们唯一的硬币是 2:

 > let b = (take 2 [1,0,0,0,0]) ++ zipWith (+) b (drop 2 [1,0,0,0,0]) in b
=> [1,0,1,0,1]

（这意味着一种生成零的方法，一种生成二的方法，一种生成四的方法。）发生的事情是 b 递归构建，因为它是自引用的，直到出现长度匹配对于 zip 评估：

 > zipWith (+) [] (drop 2 [1,0,0,0,0])
=> []
-- But we prepended [1,0] so the next `b` is [1,0]
 > zipWith (+) [1,0] (drop 2 [1,0,0,0,0])
=> [1,0]
-- But we prepended [1,0] so the next `b` is [1,0,1,0]
 > zipWith (+) [1,0,1,0] (drop 2 [1,0,0,0,0])
=> [1,0,1]
-- But we prepended [1,0] so the result matching the length is [1,0,1,0,1]

现在让我们使用这些知识来完成 solve 4 [1,2,3]:

let b = (take 3 [1,0,0,0,0]) ++ zipWith (+) b (drop 3 [1,0,0,0,0]) in b

take 3 [1,0,0,0,0] -- n+1 elements are evaluated from the infinite list
=> [1,0,0]

++       [0,0] -- drop 3 from [1,0,0,0,0]
     (+) []
     =>  []
     -- prepend [1,0,0]
     =>  [1,0,0]

++       [0,0]
     (+) [1,0,0]
     =>  [1,0]
     -- prepend [1,0,0]
     =>  [1,0,0,1,0]

这是一种生成零的方法和一种生成三的方法。下一篇：

let b = (take 2 [1,0,0,1,0]) ++ zipWith (+) b (drop 2 [1,0,0,1,0]) in b

take 2 [1,0,0,1,0]
=> [1,0]

++     [0,1,0]
   (+) []
   =>  []
   -- prepend [1,0]
   =>  [1,0]

++     [0,1,0]
   (+) [1,0]
   =>  [1,1,0]
   -- prepend [1,0]
   =>  [1,0,1,1,0]

++     [0,1,0]
   (+) [1,0,1,1,0]
   =>  [1,1,1]
   -- prepend [1,0]
   =>  [1,0,1,1,1]

这是制作 0 的一种方法，制作 2 的一种方法，制作 3 的一种方法，制作 4 的一种方法。下一个：

let b = (take 1 [1,0,1,1,1]) ++ zipWith (+) b (drop 1 [1,0,1,1,1]) in b

这是迭代次数最多的一个，因为 b 仅由一个元素构建

take 1 [1,0,1,1,1]
=> [1]

++   [0,1,1,1]
 (+) []
 =>  []
 -- prepend [1]
 =>  [1]

++   [0,1,1,1]
 (+) [1]
 =>  [1]
 -- prepend [1]
 =>  [1,1]

++   [0,1,1,1]
 (+) [1,1]
 =>  [1,2]
 -- prepend [1]
 =>  [1,1,2]

++   [0,1,1,1]
 (+) [1,1,2]
 =>  [1,2,3]
 -- prepend [1]
 =>  [1,1,2,3]

++   [0,1,1,1]
 (+) [1,1,2,3]
 =>  [1,2,3,4]
 -- prepend [1]
 =>  [1,1,2,3,4]

这是制作 0 的 1 种方法、制作 1 的 1 种方法、制作 2 的 2 种方法、制作 3 的 3 种方法和制作 4 的 4 种方法。

Haskell: 如何记忆这个算法？

Haskell: How to memoize this algorithm?

algorithm

performance

haskell

memoization

dynamic-programming