我在寻找一个很好的解决方案，找到了以下代码（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])
我理解代码的字面含义没有问题，但我不理解它为什么工作。
有人能帮忙吗？
最佳答案
要获得所有元素等于“a”或“b”或“c”（我们的硬币）总和为“x”的可能集合，您可以：
取所有这些集合的总和为x-a，并为每个集合添加一个额外的“a”。
取所有这些集合的总和为x-b，并在每个集合中添加一个额外的“b”。
取所有这些集合的总和为x-c，并在每个集合中添加一个额外的“c”。
所以你能得到x的方法的数量是你能得到x-a，x-b和x-c的方法的数量之和。
ways[i]+=ways[i-coin]
休息是简单的复发。
额外提示：
在开始时，你可以用一种方法（空集合）得到和零的集合。
ways = [1]+[0]*target
关于python - 了解变革算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14992411/