函数范式中的动态规划

functional-programming java scala dynamic-programming

2022-09-02 00:16:34

我正在研究欧拉计划的第三十一个问题，它询问，使用任意数量的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)

尽管它运行得足够快，但效率相对较低，调用该函数大约560万次。f

我看到其他人在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次。

虽然我显然可以使用对象或多或少地将其逐字翻译成Scala，但是否有一种惯用的函数式方法可以使用不可变的数据结构来做到这一点，最好具有类似的简洁性和性能？Array

我已经尝试过，但陷入了试图递归更新之前，我决定我可能只是以错误的方式接近它。List

答案 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

和的定义不是必需的 - 我可以很容易地用和替换它们，但我认为这样更清晰（更有效）。lowerhigherstream take coinstream drop coin

答案 2

我对Scala的了解还不够多，无法对此进行具体评论，但是将DP解决方案转换为递归解决方案的典型方法是记忆化（使用 http://en.wikipedia.org/wiki/Memoization）。这基本上是为域的所有值缓存函数的结果

我也发现这一点 http://michid.wordpress.com/2009/02/23/function_mem/。呵呵