EDPC H - Grid 1

グリッド1

考え方

ABCでいうと、D問題級。

動的計画法における考え方自体は単純。
もしかしたら、DP コンテストで一番簡単かもしれない。
高校数学でも典型問題である。
（組み合わせを駆使して解くことが多いが）

「左上から順に、そのマスまでの経路数を全部埋めていく」だけ。
しかも、その経路数を求める計算は、左から来るものと上から来るものを加算するだけ。

例えば入力例1ならこういう表を作るだけ。

ただし、まず、二次元的に継承する動的計画法自体が書きなれていなければ大変。
さらに、

など、実装上気を配らなくてはいけない箇所がたくさんある。
トドメに、「答えは非常に大きくなりうるので、$10^9+7$ で割った余りを求めてください。」の指示。
もちろん最後だけでなく途中もとんでもなく大きくなるので、剰余類環の考えを用いる。

インラインDPにもできる。
（といっても、元の値への変更はしているので、インプレースという方が正しいか？）
とはいえ、グリッド問題なので、普通に二次元でやる方がしっくりくる。

計算量は $O(HW)$。

入力を受け取る。

h: 3
w: 4
a:
  ...#
  .#..
  ....

dp[i][j] を、i 行目 j 列目にたどり着く方法の数とする。
最初に dp[0][0] = 1 とする。

各マスについて、壁 # なら dp[i][j] = 0 にする。
壁でなければ、上から来る方法の数と左から来る方法の数を足す。

入力例1では、DP テーブルは次のようになる。

最下段最右列の値 dp[2][3] の $3$ が答え。

答えは $10^9+7$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を % 1000000007 する。

特になし。