gpt4 book ai didi

haskell - 计算 Haskell 中的变化

转载 作者:行者123 更新时间:2023-12-04 12:40:24 27 4
gpt4 key购买 nike

我遇到了以下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 不太清楚, 尽管。它以某种方式使用每个硬币的值(value)从硬币列表中提取元素?我正在努力寻找它的直观含义。
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] .

我们通过 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 - 计算 Haskell 中的变化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31487832/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com