python - 欧拉计划 31 : Understanding Program Solution

Question

我正在尝试了解 project euler #31 的解决方案我在论坛上找到了。

问题是我们得到了具有以下值的硬币:

coins=[1,2,5,10,20,50,100,200]

我们的任务是生成达到 200 的所有可能方法。例如，10*10+100=200 就是一种可能的方法。

1. 问题 2:下面的代码是如何工作的!与我的方法相比，它看起来非常优雅、简单明了，而且运行速度更快。

在浏览论坛时，我找到了这个解决方案:

p_list = [1, 2, 5, 10, 20, 50, 100, 200]
case_num = [1] + [0] * 200
for i in p_list:
    for j in range(1, 201):
        if i <= j:
            case_num[j] += case_num[j-i]
print case_num[200]

第一行只是硬币值(value)的列表。第二行是创建一个 1 后跟 200 个 0 的数组。但是接下来的四行让我感到困惑。我认为它增加了数组中可能的方法数，因此 case_num[200] 将给出列表中的最后一个条目，但我不知道它是如何工作的。

Answer 1

正如您所说，这是一个非常好的解决方案。该代码通过每次迭代 1-200 与每种硬币面额建立在自身之上。

case_num 数组最初由 [1, 0, 0, 0, 0, 0...0, 0, 0] 组成

这些数字(除了最初的 1)的意思是您可以通过多少种方式来达到给定的总数(由数字的索引)使用到目前为止你已经迭代过的 p_list 中的硬币。

p_list 中的第一个硬币是 1。因此，如果 1 可以放入索引中，那么您可以将前一个索引中的值添加到当前索引中。这是可行的，因为如果有 5 种已知的方法可以达到 25，而你刚找到大小为 1 的硬币，那么也有 5 种方法可以达到 26。[前 5 种达到 25 的方法中的每一种] + 一个 1 硬币.

因此，在用 1 进行迭代后，您将得到 [1, 1, 1, 1, 1...1, 1]

现在您的硬币数量增加了。这次你使用的是 2 的硬币。让我们再看一遍这个过程。如果 2 小于索引，则将到达前一个索引的方法数添加到当前索引。

例如，2 不适合索引 1，但适合索引 2。因此您刚刚创建了一种从 0 到 2 的新方法，因此您采用了所有可以达到 0 的方法并将它们添加到您的当前索引。在索引 27 上，2 适合索引，因此您采用可以达到 25 的方法数并将它们添加到 27，因为现在您有(所有这些方法可以达到 25 + 一个 2 硬币)+(所有方法你必须达到 27 才能知道你有大小为 2 的硬币)。

因此，在用 2 进行迭代后，您将得到 [1, 1, 2, 2, 3, 3, 4, 4...]

如果您仍然遇到问题，尝试完成整个程序可能是值得的(可能减少总数，如 50 而不是 200)。