理解找零算法

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

这段代码的主要意思是：每一步都有 ways 种方法来找零，针对金额 i 和硬币 [1,...coin]。

在第一次迭代时，你只有面值为 1 的硬币。很明显，只有一种方法可以用这些硬币找零，针对任何目标金额。在这一步，ways 数组看起来像 [1,...1]（对于从 0 到 target 的所有目标，只有一种方法）。

在下一步，我们把面值为 2 的硬币加入到之前的硬币集合中。现在我们可以计算从 0 到 target 的每个目标金额有多少种找零组合。显然，组合的数量只会在目标金额大于等于 2 时增加（或者说是新加入的硬币）。所以对于目标金额等于 2，组合的数量将是 ways[2](旧) + ways[0](新)。一般来说，每当 i 等于新加入的硬币时，我们需要在之前的组合数量上加 1，因为新的组合只会由一枚新硬币组成。

对于 target 大于 2 的情况，答案将是“所有小于 coin 的硬币组合出 target 金额”的总和，加上“所有小于 coin 的硬币组合出 coin 金额”的总和。

这里我描述了两个基本步骤，但我希望你能轻松理解这个过程。

让我给你展示一个计算树，针对 target = 4 和 coins=[1,2]：

给定硬币 [1,2] 的 ways[4] =

给定硬币 [1] 的 ways[4] + 给定硬币 [1,2] 的 ways[2] =

1 + 给定硬币 [1] 的 ways[2] + 给定硬币 [1,2] 的 ways[0] =

1 + 1 + 1 = 3

所以有三种找零的方法： [1,1,1,1], [1,1,2], [2,2]。

上面的代码和递归解决方案是完全等价的。如果你理解了 递归解决方案，我敢打赌你也能理解上面的解决方案。

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]

Answer 3

要找出所有可能的组合，使得元素等于'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