ScalaでProject Euler（114）

Problem 76

f(n, m)は同じ引数で何度も呼び出されます。例えば、f(1, 1)は169229875回呼ばれるようです。fは引数が同じならいつも同じ答えを返すので、それを記録しておけばよいです。メモ化ですね。これで3msくらいです。本当はもっと速い方法があるのですが、それは78に残しておきます。

import scala.collection.mutable.Map
import scala.testing.Benchmark

object DivInteger {
    val memo = Map[(Int,Int),Long]()
    
    def apply(n :Int) :Long = f(n, n)
    def clear() = memo.clear()
    
    private def f(n :Int, m :Int) :Long =
        if(n == 0)
            1
        else if(memo.contains((n, m)))
            memo((n,m))
        else {
            val s = Iterator.range(1, m + 1).
                            map(k => f(n - k, k.min(n - k))).sum
            memo((n,m)) = s
            s
        }
}

def solve() = {
    val N = 100
    println (DivInteger(N) - 1)
    DivInteger.clear()
}

object Test extends Benchmark {
    def run() = solve
}

println (Test.runBenchmark(10))