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

• 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` with values `{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}`, 0 and 1 represent for empty and obstacle respectively

• Expected 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 = 1`, `cache[i]` and `cache[j]` are base cases

• `cache[rows-1][cols-1]` is final result

``````public class DP_UniquePaths_Obstacles {
int countUniquePaths(int[][] A) {
if (A == 1) return 0;

int rows = A.length;
int cols = A.length;
int[][] cache = new int[rows][cols];

cache = 1;

for (int i = 1; i < rows; i++) {
if (A[i] == 0)
cache[i] = cache[i-1];
}

for (int j = 1; j < cols; j++) {
if (A[j] == 0)
cache[j] = cache[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