多次元の動的計画法
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()