相关疑难解决方法(0)

我正在寻找关于项目欧拉的问题三十一,请问,有多少不同的方法可以使用任意数量的1p,2p,5p,10p,20p,50p,£1(100p)和£的硬币赚2英镑2(200p).

有递归解决方案,例如Scala中的这个解决方案(由Pavel Fatin提供)

def f(ms: List[Int], n: Int): Int = ms match {
  case h :: t =>
    if (h > n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n)
  case _ => 0
} 
val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)

虽然运行速度足够快,但它的效率相对较低,调用f函数大约560万次.

我看到了其他用Java编写的动态编程解决方案(来自葡萄牙的wizeman)

final static int TOTAL = 200;

public static void main(String[] args) {
    int[] coins = {1, 2, 5, 10, 20, …