読者です 読者をやめる 読者になる 読者になる

AtCoder ABC D: 経路

AtCoder メモ化再帰 動的計画法 深さ優先探索 漸化式

問題

D: 経路 - AtCoder Beginner Contest 037 | AtCoder

解法

以下をポイントにして動的計画法により解く。

  • 求めたいもの: 経路数
  • マスを進む度に変わるもの: (i, j) 現在いるマスがi行j列のマス
  • 進めるマスが無くなったらを抜ける条件にして再帰関数で実装
  • dp[i, j] = 経路数とする

漸化式を考える。

漸化式

f(i, j)の経路数は、上下左右の4つのマスの経路数の和に1加えた数になる。1加えるのは、今回の問題では1マスも動かなくて良いという条件によるものだ。これによって漸化式は以下のようになる。


f(i, j) = f(i + 1, j) + f(i, j + 1) + f(i - 1, j) + f(i, j - 1) + 1


ただし、上下左右全てのマスに進めるとは限らないので、毎回チェックする必要がある。

ソースコード