AtCoder ABC D: 経路
問題
D: 経路 - AtCoder Beginner Contest 037 | AtCoder
解法
以下をポイントにして動的計画法により解く。
- 求めたいもの: 経路数
- マスを進む度に変わるもの: (i, j) 現在いるマスがi行j列のマス
- 進めるマスが無くなったらを抜ける条件にして再帰関数で実装
- dp[i, j] = 経路数とする
漸化式を考える。
漸化式
f(i, j)の経路数は、上下左右の４つのマスの経路数の和に１加えた数になる。１加えるのは、今回の問題では１マスも動かなくて良いという条件によるものだ。これによって漸化式は以下のようになる。
f(i, j) = f(i + 1, j) + f(i, j + 1) + f(i - 1, j) + f(i, j - 1) + 1
ただし、上下左右全てのマスに進めるとは限らないので、毎回チェックする必要がある。
