AtCoder Educational DP Contest H問題解いてみた

今回の問題

問題文

縦 $H$ 行、横 $W$ 列のグリッドがあります。
上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ で表します。

各 $i, j$ ($1 \leq i \leq H, 1 \leq j \leq W$) について、マス $(i, j)$ の情報が文字 $a_{i,j}$ によって与えられます。

• $a_{i,j}$ が . ならば、マス $(i, j)$ は空マスです。
• $a_{i,j}$ が # ならば、マス $(i, j)$ は壁のマスです。

マス $(1, 1)$ および $(H, W)$ は空マスであることが保証されています。

太郎君は、マス $(1, 1)$ から出発し、右または下に隣り合う空マスへの移動を繰り返すことで、マス $(H, W)$ まで辿り着こうとしています。

マス $(1, 1)$ から $(H, W)$ までの太郎君の経路は何通りでしょうか？
答えは非常に大きくなりうるので、$10^9 + 7$ で割った余りを求めてください。

制約

• $H$ および $W$ は整数である。
• $2 \leq H, W \leq 1000$
• $a_{i,j}$ は . または # である。
• マス $(1, 1)$ および $(H, W)$ は空マスである。

自分の回答

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
int main() {
    int h, w;
    cin >> h >> w;
    vector<string> grid(h);
    for (int i = 0; i < h; i++) {
        cin >> grid[i];
    }
    long long dp[1001][1001];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if(i > 0 && grid[i][j] == '.' && grid[i-1][j] == '.') {
                dp[i][j] += dp[i-1][j];
                dp[i][j] %= 1000000007;
            }
            if(j > 0 && grid[i][j] == '.' && grid[i][j-1] == '.') {
                dp[i][j] += dp[i][j-1];
                dp[i][j] %= 1000000007;
            }
        }
    }
    cout << dp[h-1][w-1] << endl;


    return 0;
}

解説

dp[i][j]をi,jまでいく経路の数とする。漸化式はdp[i][j]=dp[i-1][j]+dp[i][j-1]となる。あとは枠からはみ出さないかと、割るのを忘れなければ比較的簡単である。