https://atcoder.jp/contests/dp/tasks/dp_h
前提知識
解説
https://atcoder.jp/contests/dp/submissions/3947874
mod10^9+7の数え上げはDPの可能性が高いし、マス移動でDPを使う問題は死ぬほどみたせいか、DPの定義が自然と出てくるので解説ができない。
制約もこの定義を後押ししている。
dp[y][x] := マス(y,x)に移動する経路の組合せ
dp[y][x]からの遷移を考えるとdp[y+1][x]かdp[y][x+1]がある。
この2つについて、枠内でかつ空マスであるときに遷移を行う。
mod10^9+7の扱いは、自分はmintを使っている。
たまに自力で書きたい場面が出てきたりするので、中身がわかってるとなお良し。
int H, W; string A[1010]; mint dp[1010][1010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> H >> W; rep(y, 0, H) cin >> A[y]; dp[0][0] = 1; rep(y, 0, H) rep(x, 0, W) { if (y + 1 < H and A[y + 1][x] != '#') dp[y + 1][x] += dp[y][x]; if (x + 1 < W and A[y][x + 1] != '#') dp[y][x + 1] += dp[y][x]; } cout << dp[H - 1][W - 1] << endl; }