功能范式中的动态编程

Question

我正在研究Euler项目上的问题31，它问，使用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, 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
，但是否有一种惯用的功能方法使用不可变的数据结构来做到这一点，最好具有相似的简洁性和性能？

在尝试以递归方式更新a List之前，我尝试并陷入困境，然后才决定我可能只是以错误的方式进行操作。

Answer 1

每当基于前一个元素计算数据列表的某些部分时，我都会想到Stream递归。不幸的是，这种递归不能在方法定义或函数内部发生，因此我不得不将一个函数转换为一个类以使其起作用。

class IterationForCoin(stream: Stream[Int], coin: Int) {
  val (lower, higher) = stream splitAt coin
  val next: Stream[Int] = lower #::: (higher zip next map { case (a, b) => a + b })
}
val coins = List(1, 2, 5, 10, 20, 50, 100, 200)
val result = coins.foldLeft(1 #:: Stream.fill(200)(0)) { (stream, coin) =>
  new IterationForCoin(stream, coin).next
} last

的定义lower，并higher没有必要-我可以很容易地替换他们stream take coin和stream drop coin，但我认为这是一个更清晰一点（和更有效）这种方式。