I’ve been trying to solve Atcoder’s dp problem collection. I started doing a problem called “Grid 1” (https://atcoder.jp/contests/dp/tasks/dp_h) but my solution gave AC on only half of the test cases. Could anyone please help me figure out my mistake?
I’ve defined dp[i][j] as being the total number of ways to reach the i, j position from 0, 0. I’m using 0-based indexing everywhere…
h, w = map(int, input().split()) grid =  for i in range(h): r = input() curr =  for ch in r: if ch == ".": curr +=  else: curr +=  grid.append(curr) def outofbounds(i, j): return (i < 0 or j < 0) or (i >= h or j >= w) dp = [[None for x in range(w)] for y in range(h)] dp = 1 def recursive(i, j): if outofbounds(i, j): return 0 elif dp[i][j] is not None: return dp[i][j] elif grid[i][j] == 1: dp[i][j] = 0 return 0 else: dp[i][j] = recursive(i-1, j) + recursive(i, j-1) return dp[i][j] print(recursive(h-1, w-1))