我正在看 Project Euler 上的 问题31,它问:使用任意数量的1p、2p、5p、10p、20p、50p、£1(100p)和£2(200p)硬币,有多少种不同的方法可以组成 £2。
有递归解决方案,例如 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, 50, 100, 200};
int[] ways = new int[TOTAL + 1];
ways[0] = 1;
for (int coin : coins) {
for (int j = coin; j <= TOTAL; j++) {
ways[j] += ways[j - coin];
}
}
System.out.println("Result: " + ways[TOTAL]);
}
这种方法更高效,内部循环只需要进行1220次。
虽然我可以使用Array对象将其逐字翻译成Scala,但是否有一种惯用的函数式方法,可以使用不可变数据结构来做到这一点,最好具有类似的简洁性和性能?
我尝试过在递归更新列表之前卡住了,后来认为我可能只是走错了路。