In this article, we will learn to resolve the Unique Paths with Obstacles problem in Java by using a dynamic programming algorithm

## Problem

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

Write an algorithm to count the number of unique paths to reach 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

## Example

Input

`A[3][3]`

with values`{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}`

, 0 and 1 represent for empty and obstacle respectivelyExpected output

`2`

## Approach: 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

```
public class DP_UniquePaths_Obstacles {
int countUniquePaths(int[][] A) {
if (A[0][0] == 1) return 0;
int rows = A.length;
int cols = A[0].length;
int[][] cache = new int[rows][cols];
cache[0][0] = 1;
for (int i = 1; i < rows; i++) {
if (A[i][0] == 0)
cache[i][0] = cache[i-1][0];
}
for (int j = 1; j < cols; j++) {
if (A[0][j] == 0)
cache[0][j] = cache[0][j-1];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (A[i][j] == 0)
cache[i][j] = cache[i-1][j] + cache[i][j-1];
}
}
return cache[rows-1][cols-1];
}
public static void main(String[] args) {
DP_UniquePaths_Obstacles uniquePaths = new DP_UniquePaths_Obstacles();
int[][] A = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
System.out.println(uniquePaths.countUniquePaths(A));
}
}
```

- Output

```
2
```

- Time complexity is O(mn) and space complexity is O(mn), where m is the number of rows, and n is the number of columns