多次元の動的計画法

H - Grid 1

O(N)

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    H, W = list(map(int, input().split()))
    G = []
    for _ in range(H):
        S = str(input())
        G.append(S)
    dp = []
    for i in range(H):
        dp.append([0]*W)

    dp[0][0] = 1

    MOD  = 10**9+7
    for i in range(H):
        for j in range(W):
            if G[i][j] == '#' or (i==0 and j==0):
                continue

            if i > 0:
                dp[i][j] += dp[i-1][j]
            if j > 0:
                dp[i][j] += dp[i][j-1]
            
            dp[i][j] %= MOD

    print(dp[H-1][W-1])    

# エントリポイント
if __name__ == '__main__':
    main()