[Project Euler] Problem 18

Problem 18

n段目では、(n-1)段目で左右を選ぶ選択で大きな方を選ぶ、というのを再帰的にやれば良いが、計算時間を減らす為に、Problem 15と同様にメモ化する。

import scala.collection.mutable.HashMap
object P018 {

  val input:Array[String] = Array(
"75",
"95 64",
...中略...
"63 66 04 68 89 53 67 30 73 16 69 87 40 31",
"04 62 98 27 23 09 70 98 73 93 38 53 60 04 23") // y=0
  val data:Array[Array[Int]] = input.map{s => s.split(" ").map{x => x.toInt}}
  val height = input.size
  def value(x:Int,y:Int):Int = data(height-1-y)(x)
  val map:HashMap[Tuple2[Int,Int],Int] = new HashMap()
  def search(x:Int,y:Int):Int = map.get(Tuple2(x,y)) match {
    case Some(x) => x
    case None => (x,y) match {
      case (_,0) => {
        val v = value(x,y)
        map.put(Tuple2(x,y),v)
        v
      }
      case _ => {
        val s0 = value(x,y)
        val s1 = search(x,y-1)
        val s2 = search(x+1,y-1)
        val v = if (s1>s2) s0+s1 else s0+s2
        map.put(Tuple2(x,y),v)
        v
      }
    }
  }
  def main(args:Array[String]) {
    println(search(0,height-1))
  }
}