了解变革算法

Question

我正在寻找一个很好的解决变更问题的方法,我找到了这个代码(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])

我理解代码的字面意思是没有问题,但我无法理解为什么它有效.有人可以帮忙吗？

Answer 1

要获得所有可能的元素等于'a'或'b'或'c'(我们的硬币)总和为'X'的集合,您可以:

• 取所有总和为Xa的集合,并为每个集合添加额外的"a".
• 取所有总计为Xb的集合,并为每个集合添加额外的"b".
• 取所有总计为Xc的集合,并为每个集合添加额外的"c".

因此,获得X的方式数量是获得Xa和Xb以及Xc的方式数量的总和.

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

休息是简单的复发.

额外提示:在开始时你可以用一种方式设置零和(空集)

ways = [1]+[0]*target

Answer 2

这是动态编程的经典示例.它使用缓存来避免两次计算3 + 2 = 5之类的陷阱(因为另一种可能的解决方案:2 + 3).递归算法陷入了陷阱.让我们专注于一个简单的例子,其中target = 5和coins = [1,2,3].您发布的代码重要:

1. 3 + 2
2. 3 + 1 + 1
3. 2 + 2 + 1
4. 1 + 2 + 1 + 1
5. 1 + 1 + 1 + 1 + 1

而递归版本计数:

1. 3 + 2
2. 2 + 3
3. 3 + 1 + 1
4. 1 + 3 + 1
5. 1 + 1 + 3
6. 2 + 1 + 2
7. 1 + 1 + 2
8. 2 + 2 + 1
9. 2 + 1 + 1 + 1
10. 1 + 2 + 1 + 1
11. 1 + 1 + 2 + 1
12. 1 + 1 + 1 + 2
13. 1 + 1 + 1 + 1 + 1

递归代码:

coinsOptions = [1, 2, 3]
def numberOfWays(target):
    if (target < 0):
        return 0
    elif(target == 0):
        return 1
    else:
        return sum([numberOfWays(target - coin) for coin in coinsOptions])
print numberOfWays(5)

动态编程:

target = 5
coins = [1,2,3]
ways = [1]+[0]*target
for coin in coins:
    for i in range(coin, target+1):
        ways[i]+=ways[i-coin]
print ways[target]