Euler31项目：了解程序解决方案

Question

我试图理解一种解决方案 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]

第一行只是硬币值的列表。第二行是创建一个以1为1的数组，其次是200 0。但是接下来的四行使我感到困惑。我认为它正在增加数组中可能的方法数量，因此Case_num [200]将提供列表中的最后一个条目，但我不知道它是如何工作的。

Answer 1

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

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

这些数字（除了初始1）的意思是，您可以使用P_LIST中的硬币在迄今为止遍历的P_LIST中使用硬币来建立几种方法（由数字的索引表示）。

p_list中的第一枚硬币为1。因此，如果1可以安装在索引中，则将其在上一个索引中获取并将其添加到当前索引中。这起作用是因为如果有5种已知的方法可以达到25，而您刚刚找到了1号尺寸的硬币，那么也将有5种方法可以达到26。 。

因此，在使用1迭代后，您最终会得到[1、1、1、1、1 ... 1、1

现在您在硬币中移动。这次，您使用的硬币为2。让我们仔细阅读该过程1。如果2较少，则索引，则将到达上一个索引的方法添加到当前索引。

例如，2不适合索引1，但确实适合索引2。因此，您只是创建了一种从0到2的新方法，因此您可以采用所有可以达到0的方法并将其添加到当前索引中。在索引27上，索引中有2个适合，因此您采用了可以达到25的方式并将它们添加到27的数量，因为现在您有（所有这些方法可以达到25 +一个2硬币） +（所有的方式）您必须达到27，然后才知道自己有2个尺寸的硬币）。

因此，在使用2迭代后，您最终将得到[1、2、2、3、3、4、4 ...

如果您仍然遇到麻烦，那么尝试浏览整个程序可能是值得的（也许总数减少了50，而不是200个）。