1. 首页
  2. 问题
  3. 了解变更算法
一尘不染

了解变更算法

algorithm

我一直在寻找一种解决变更问题的好方法，并且找到了以下代码（Python）：

target = 200
coins = [1,2,5,10,20,50,100,200]
ways = [1]+[0]*target
for coin in coins:
    for i in range(coin,target+1):
        ways[i]+=ways[i-coin]
print(ways[target])

我对理解代码的字面意义没有任何疑问，但是我不明白为什么它会起作用。有人可以帮忙吗？


阅读 175

收藏
2020-07-28

共1个答案

一尘不染

要获得元素等于“ a”，“ b”或“ c”（我们的硬币）的所有可能的集合，其总和为“ X”，您可以：

  • 取所有总计为Xa的集合，并为每个集合添加一个额外的“ a”。
  • 取所有总计为Xb的集合，并为每个集合添加一个额外的“ b”。
  • 取所有总计为Xc的集合，并为每个集合添加一个额外的“ c”。

因此，获得X的方法数量等于获得Xa和Xb与Xc的方法数量之和。

ways[i]+=ways[i-coin]

休息就是简单的复发。

额外提示：开始时，您可以以一种完全正确的方式设置总和为零（空集）

ways = [1]+[0]*target
2020-07-28