动态规划的功能范式 [英] Dynamic programming in the functional paradigm

问题描述

我正在第三十一题关于欧拉计划，询问有多少种不同的方式可以使用1p，2p，5p，10p，20p，50p，1英镑（100p）和2英镑（200p）的任意数量的硬币制造2英镑。

有递归的解决方案，例如Scala中的这个（Pavel Fatin信用）

pre $ def f（ms：List [Int]，n：Int）：Int = ms match {
case h :: t => （h> n）0 else if（n == h）1 else 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）。 code> 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; （int j = coin; j <= TOTAL; j ++）{
ways [j] + = ways [j - 硬币];
}
}

System.out.println（Result：+ ways [TOTAL]）;
}

这样做效率更高，并且只传递1220次内循环。 p>

虽然我可以使用 Array 对象或多或少逐字逐句翻译为Scala，但是有没有一种惯用的函数式这使用不可变的数据结构，最好具有类似的简洁性和性能？我试过并试图递归更新一个 List 解决方案

无论何时数据列表的某些部分是根据之前的元素计算，我想到 Stream 递归。不幸的是，这种递归不能在方法定义或函数内部发生，所以我不得不将一个函数变成一个类来使其工作。

  class IterationForCoin（stream：Stream [Int]，coin：Int）{
 val（lower，higher）= stream splitAt coin 
 val next：Stream [Int] = lower＃:::（higher zip下一个地图{情况（a，b）=> a + b}）
} 
 val硬币=列表（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 
  

的低于和高于是不必要的 - 我可以很容易地用替换它们。 和 stream drop coin ，但我认为这样做更清晰一些（并且更高效）。

I'm looking at Problem thirty one on Project Euler, which asks, how many different ways are there of making £2 using any number of coins of 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

There are recursive solutions, such as this one in Scala (credit to 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)

and although it runs fast enough, it's relatively inefficient, calling the f function around 5.6 million times.

I saw someone else's solution in Java which was programmed dynamically (credit to wizeman from Portugal)

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]);
}

This is much more efficient and passes the inner loop only 1220 times.

While I could obviously translate this more or less verbatim into Scala using Array objects, is there an idiomatic functional way to do this using immutable data structures, preferably with similar conciseness and performance?

I have tried and become stuck trying to recursively update a List before deciding I'm probably just approaching it the wrong way.

解决方案

Whenever some part of a list of data is computed based on a previous element, I think of Stream recursion. Unfortunately, such recursion cannot happen inside method definitions or functions, so I had to turn a function into a class to make it work.

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

The definitions of lower and higher are not necessary -- I could easily replace them with stream take coin and stream drop coin, but I think it's a little clearer (and more efficient) this way.

这篇关于动态规划的功能范式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！