计算 Haskell 的变化

Question

我遇到了以下counting change的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 是初始值？代表什么？

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 returns 修改列表而不是改变旧列表。至于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的初始化和硬币上的for循环，变化是初始列表是无限的而不是有限的（因为懒惰让我们这样做）。

计算 Haskell 的变化

Counting change in Haskell

haskell

dynamic-programming