function范式中的动态编程
我正在寻找关于项目欧拉的问题三十一 ，请问，有多少不同的方法可以使用任意数量的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，但使用不可变数据结构是否有一种惯用的function方法，最好具有类似的简洁性和性能？
我已经尝试过，在决定我可能只是以错误的方式接近它之前，试图以递归方式更新List 。
每当基于前一个元素计算数据列表的某些部分时，我就会想到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替换它们，但我认为这样更清晰（也更有效）。
我不太了解Scala对此有何具体评论，但将DP解决方案转换为递归方法的典型方法是记忆（使用http://en.wikipedia.org/wiki/Memoization ）。 这基本上是为域的所有值缓存函数的结果
我也发现了这个问题http://michid.wordpress.com/2009/02/23/function_mem/ 。 HTH
function性动态编程实际上可以在惰性语言中非常漂亮，例如Haskell（在Haskell wiki 上有一篇关于它的文章 ）。 这是针对该问题的动态编程解决方案：
import Data.Array makeChange :: [Int] -> Int -> Int makeChange coinsList target = arr ! (0,target) where numCoins = length coinsList coins = listArray (0,numCoins-1) coinsList bounds = ((0,0),(numCoins,target)) arr = listArray bounds . map (uncurry go) $ range bounds go in | i == numCoins = 0 | otherwise = let c = coins ! i in case c `compare` n of GT -> 0 EQ -> 1 LT -> (arr ! (i, nc)) + (arr ! (i+1,n)) main :: IO () main = putStrLn $ "Project Euler Problem 31: " ++ show (makeChange [1, 2, 5, 10, 20, 50, 100, 200] 200)
不可否认，这使用O（ cn ）内存，其中c是硬币数， n是目标（与Java版本的O（ n ）内存相对）; 要做到这一点，你必须使用一些捕获可变状态的技术（可能是一个STArray ）。 但是，它们都在O（ cn ）时间运行。 我们的想法是几乎直接递归地对递归解决方案进行编码，但不是在go中递归，而是在数组中查找答案。 我们如何构建数组？ 通过调用每个索引。 由于Haskell是懒惰的，它只会在被要求时计算，因此动态编程所需的评估顺序都是透明处理的。
感谢Scala的名字参数和lazy val ，我们可以在Scala中模仿这个解决方案：
class Lazy[A](x: => A) { lazy val value = x } object Lazy { def apply[A](x: => A) = new Lazy(x) implicit def fromLazy[A](z: Lazy[A]): A = z.value implicit def toLazy[A](x: => A): Lazy[A] = Lazy(x) } import Lazy._ def makeChange(coins: Array[Int], target: Int): Int = { val numCoins = coins.length lazy val arr: Array[Array[Lazy[Int]]] = Array.tabulate(numCoins+1,target+1) { (i,n) => if (i == numCoins) { 0 } else { val c = coins(i) if (c > n) 0 else if (c == n) 1 else arr(i)(nc) + arr(i+1)(n) } } arr(0)(target) } // makeChange(Array(1, 2, 5, 10, 20, 50, 100, 200), 200)
Lazy类对仅按需评估的值进行编码，然后我们构建一个完整的数组。 这两个解决方案实际上只能立即达到10000的目标值，虽然要大得多，但你会遇到整数溢出或（至少在Scala中）堆栈溢出。
好的，这是Pavel Fatin代码的备忘版本。 我正在使用Scalaz memoization东西，尽管编写自己的memoization类非常简单。
import scalaz._ import Scalaz._ val memo = immutableHashMapMemo[(List[Int], Int), Int] def f(ms: List[Int], n: Int): Int = ms match { case h :: t => if (h > n) 0 else if (n == h) 1 else memo((f _).tupled)(ms, n - h) + memo((f _).tupled)(t, n) case _ => 0 } val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)
为了完整起见，以上是不使用Stream的答案的略微变体：
object coins { val coins = List(1, 2, 5, 10, 20, 50, 100, 200) val total = 200 val result = coins.foldLeft(1 :: List.fill(total)(0)) { (list, coin) => new IterationForCoin(list, coin).next(total) } last } class IterationForCoin(list: List[Int], coin: Int) { val (lower, higher) = list splitAt coin def next (total: Int): List[Int] = { val listPart = if (total>coin) next(total-coin) else lower lower ::: (higher zip listPart map { case (a, b) => a + b }) } }