Given a 2D array A[M][N], aka Grid / Maze / Matrix

Write an algorithm to count the number of unique paths to reach to A[M-1][N-1] from A[0][0]

At any cell (x, y), you can either go to (x+1, y) or (x, y+1) if there's no obstacle


Input A[3][3] with values {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0 and 1 represent for empty and obstacle respectively

Expected output 2


Using dynamic programming bottom-up

  • Fill up matrix cache[i][j] to count unique paths to (i,j)
  • cache[i][j] = cache[i-1][j] + cache[i][j-1] for each (i,j) with A[i][j] as 0
  • cache[0][0] = 1, cache[i][0] and cache[0][j] are base cases
  • cache[rows-1][cols-1] is final result