プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q15:階段で立ち話。

Q: 10段の階段の上下にそれぞれ人がいて、最大3段飛ばしで移動したとき、2人が同じ段に止まる移動方法は何通りか求める。

メモ化してるから結構早い

val range = 1 to 4
val memo = scala.collection.mutable.Map.empty[(Int,Int),Int]
def move(a:Int, b:Int):Int = {
  if(a > b) 0
  else if(a == b) 1
  else if(memo.isDefinedAt((a,b))) memo((a,b))
  else {
    val res = range.fold(0){(z,up) => range.fold(z){(zz,down) => zz + move(a+up, b-down)}}
    memo += ((a,b) -> res)
    res
  }
}
move(0,10)