ScalaでProject Euler（102）

Scala

Problem 67

メモ化ですね。

   3
  7 4
 2 4 6
8 5 9 3

一番下はそのままにして、2番目の左端、2を考えます。2の下は8と5ですが、トータルで最大になるのは8を選んだ時です。それを2に加えます。

    3
   7 4
 10 4 6
8  5 9 3

この列を同じように処理すると、

    3
   7  4
 10 13 15
8  5  9  3

次の列の左端7について、その下の10と13で13が大きいのでこれを足して20。残りも同様に処理して、

    23
   20 19
 10 13 15
8  5  9  3

結局、23となります。計算量は整数の個数に比例します。

val s = io.Source.fromFile("triangle.txt")
val a = s.getLines.toArray.map(_.split(' ').map(_.toInt))
val N = a.size
for(y <- N - 2 to 0 by -1; x <- 0 to y)
    a(y)(x) += a(y+1)(x).max(a(y+1)(x+1))
println (a(0)(0))