您正在寻找的是 动态编程 。
实际上，您不必为每个可能的值枚举所有可能的组合，因为您可以将其构建在先前的答案之上。
您的算法需要采用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]，我不确定如何快速检查新集所覆盖的范围，否则实际上效率更高。
