在Haskell中计算找零

Question

我找到了一个解决 找零问题 的动态规划方案，具体内容如下：

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是初始值？它代表什么？

- user1953221

Answer 1

这是该问题的命令式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 个元素，然后我们必须实现 solutions[i] += solutions[i - coin]。

我们通过 take c oldlist 实现不变的部分，并通过 zipWith (+) newlist (drop 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 的初始化和对硬币的循环，不同之处在于初始列表是无限而不是有限（因为惰性使我们可以这样做）。

- András Kovács