找到可以进行1到99美分的零钱的最少数量的硬币

找到可以进行1到99美分的零钱的最少数量的硬币

您正在寻找的是 动态编程 。

实际上，您不必为每个可能的值枚举所有可能的组合，因为您可以将其构建在先前的答案之上。

您的算法需要采用2个参数：

• 可能的硬币值列表，在这里

  [1, 5, 10, 25]

• 覆盖范围，在这里

  [1, 99]

目标是计算此范围所需的最小硬币集。

最简单的方法是以自下而上的方式进行：

Range     Number of coins (in the minimal set)          1   5   10   25[1,1]     1[1,2]     2[1,3]     3[1,4]     4[1,5]     5[1,5]*    4   1  * two solutions here[1,6]     4   1[1,9]     4   1[1,10]    5   1  * experience tells us it's not the most viable one :p[1,10]    4   2  * not so viable either[1,10]    4   1   1[1,11]    4   1   1[1,19]    4   1   1[1,20]    5   1   1         * not viable (in the long run)[1,20]    4   2   1         * not viable (in the long run)[1,20]    4   1   2

这有点容易，在每个步骤中，我们最多可以添加一个硬币，我们只需要知道在哪里。这归结为以下事实：范围

[x,y]

包含在其中，

[x,y+1]

因此for的最小集

[x,y+1]

应包括for
的最小集

[x,y]

。

正如您可能已经注意到的那样，有时会有些犹豫不决，即多套硬币的数量相同。在这种情况下，只能稍后决定丢弃哪一个。

我认为，当注意到添加硬币通常可以使您覆盖所添加硬币的范围更大时，应该可以改善其运行时间。

例如，请注意：

 [1,5]    4*1  1*5 [1,9]    4*1  1*5

我们添加了镍来覆盖，

[1,5]

但这

[1,9]

免费提供给我们！

但是，当处理

[2,3,5,10,25]

覆盖的令人毛骨悚然的输入集时

[2,99]

，我不确定如何快速检查新集所覆盖的范围，否则实际上效率更高。