计算Haskell的变化

Question

我遇到了计算变化的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返回一个修改后的列表而不是改变旧的列表。对于 Haskell 版本，结果在开始处应该有一个未更改的部分，直到第coin- 个元素，之后我们必须实现solutions[i] += solutions[i - coin].

我们通过 来实现未改变的部分take c oldlist，通过 来实现修改的部分zipWith (+) newlist (drop c oldlist)。i在修改的部分中，我们将旧列表的第 - 个元素和i - coin结果列表的第 - 个元素添加在一起。索引的移动隐含在dropandtake运算中。

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

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 循环，变化是初始列表是无限的而不是有限的（因为懒惰让我们这样做）。