计算Haskell中的变化

我遇到了DP计数变化问题的以下解决方案：

count' :: Int -> [Int] -> Int
count' cents coins = aux coins !! cents
  where aux = foldr addCoin (1:repeat 0)
          where addCoin c oldlist = newlist
                  where newlist = (take c oldlist) ++ zipWith (+) newlist (drop c oldlist)

它的运行速度比我的天真的自顶向下递归解决方案快得多，我仍然试图理解它。

我得到这个给出的硬币列表， aux计算每个正整数的解决方案。 因此，一个金额的解决方案是索引该位置的列表。

不过，我不太清楚addCoin 。 它以某种方式使用每枚硬币的价值来从硬币列表中抽取元素？ 我努力为它找到一个直观的意义。

在aux的折叠也将我的大脑连结起来。 为什么1:repeat 0的初始值？ 它代表什么？

---

它是针对该问题的命令式DP算法的直接翻译，看起来像这样（在Python中）：

def count(cents, coins):
    solutions = [1] + [0]*cents # [1, 0, 0, 0, ... 0]
    for coin in coins:
        for i in range(coin, cents + 1):
            solutions[i] += solutions[i - coin]
    return solutions[cents]

特别是， addCoin coin solutions对应于

for i in range(coin, cents + 1):
    solutions[i] += solutions[i - coin]

除了addCoin返回一个修改列表而不是改变旧列表。 至于Haskell版本，结果在开始之前应该有一个不变的部分，直到coin th元素，然后我们必须实现solutions[i] += solutions[i - coin] 。

我们通过使用zipWith (+) newlist (drop c oldlist)实现take c oldlist和修改过的部分来实现未改变的部分。 在修改后的部分中，我们添加在一起i的旧列表的个元素和i - coin结果列表中的个元素。 指数的转移隐含在drop和take操作中。

这种移位和递归定义的一个更简单，经典的例子是斐波纳契数字：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

我们将这个命令写为

def fibs(limit):
    res = [0, 1] + [0]*(limit - 2)
    for i in range(2, limit):
        res[i] = res[i - 2] + res[i - 1]
    return res

回到硬币更换， foldr addCoin (1:repeat 0)对应于硬币上solutions和for循环的初始化，改变了初始列表是无限的而不是有限的（因为懒惰让我们这样做）。

链接地址: http://www.djcxy.com/p/27603.html

上一篇: Counting change in Haskell

下一篇: How do I add the values of checked radio buttons to a seperate element