プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q23:ブラックジャックで大もうけ!?。

Q: コインを1枚ずつ賭けていったとき、最初に10枚のコインを持ち、ゲームを24回行った時、手元にコインが残るよパターンが何通りか求める。

val memo = scala.collection.mutable.Map.empty[(Int,Int),Int]
def bet(game:Int, coin:Int):Int = {
  if(game == 0) 1
  else if(coin == 0) 0
  else {
    memo.getOrElse(game->coin, {
      val result = bet(game-1, coin+1) + bet(game-1, coin-1)
      memo + ((game -> coin)->result)
      result
    })
  }
}
bet(24,10)