[Python] Educational DP Contest H – Grid 1

問題

H – Grid 1

DP、数え上げ問題。

回答

import sys

# input処理を高速化する
input = sys.stdin.readline

def main():
    # input
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]

    MOD = 10**9 + 7

    # 0-indexed DPは0で初期化
    dp = [[0] * W for _ in range(H)]
    # DP初期条件
    dp[0][0] = 1

    # 全マス目を探索
    for i in range(H):
        for j in range(W):
            if i+1 < H and A[i+1][j] == '.':
                dp[i+1][j] += dp[i][j]
                # 計算の途中で余りをとる
                if dp[i+1][j] >= MOD:
                    dp[i+1][j] -= MOD
            if j+1 < W and A[i][j+1] == '.':
                dp[i][j+1] += dp[i][j]
                if dp[i][j+1] >= MOD:
                    dp[i][j+1] -= MOD
    
    print(dp[H-1][W-1])

main()