理解改变算法

Question

我正在寻找一个好的Change-making problem解决方案，我找到了这个代码(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’，您可以：

• 取和为X-a的所有此类集合，并为每个集合添加一个额外的'a‘。
• 获取所有求和为X-b的集合，并为每个集合添加一个额外的'b’。
• 获取所有求和为X-c的集合，并为每个集合添加额外的'c‘。

所以你可以得到X的方法的数量是你可以获得X-a，X-b和X-c的方法的数量之和。

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

Rest是简单的递归。

额外提示:在开始时，您可以通过一种方式(空集)使用sum 0进行设置。

ways = [1]+[0]*target

Answer 2

这是一个经典的dynamic programming示例。它使用缓存来避免两次计算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]

Answer 3

代码背后的主要思想如下：“在每一步都有ways的方法来改变给定硬币[1,...coin]的钱的数量”。

因此，在第一次迭代中，您只有一枚面额为1的硬币。我相信很明显，对于任何目标来说，只有一种方法可以改变只有这些硬币。在这一步中，ways数组将看起来像[1,...1] (从0到target的所有目标只有一种方式)。

下一步，我们将一枚面额为2的硬币添加到前一套硬币中。现在我们可以计算每个目标从0到target有多少个更改组合。显然，组合的数量只会增加目标>= 2 (或新添加的硬币，在一般情况下)。因此，对于等于2的目标，组合的数量将是ways[2](old) + ways[0](new)。通常，每次当i等于一个新引入的硬币时，我们需要将1添加到以前的组合数量中，其中新的组合将仅由一个硬币组成。

对于target > 2，答案将由“target amount的所有硬币少于coin的所有组合”和“coin amount的所有硬币少于coin本身的所有组合”的总和组成。

这里我描述了两个基本步骤，但我希望它很容易概括。

让我向您展示target = 4和coins=[1,2]的计算树

给定coins=1,2的

ways4 =

给定coins=1 + ways2的ways4给定coins=1,2 =

给定coins=1的1+ ways2 +给定coins=1,2 =的方式

1+1+1=3

因此，有三种方式可以进行更改：[1,1,1,1], [1,1,2], [2,2]。

上面给出的代码完全等同于递归解决方案。如果你理解the recursive solution，我打赌你也理解上面给出的解决方案。