In this artcile, we will learn to resolve the Unique Paths without Obstacles 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)

## Example

Input

`A[3][3]`

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

Expected output

`6`

## 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)`

`cache[i][0]`

and`cache[0][j]`

are base cases`cache[rows-1][cols-1]`

is final result

```
public class DP_UniquePaths_WithOutObstacles {
int countUniquePaths(int[][] A) {
int rows = A.length;
int cols = A[0].length;
int[][] cache = new int[rows][cols];
for (int i = 0; i < rows; i++) {
cache[i][0] = 1;
}
for (int j = 0; j < cols; j++) {
cache[0][j] = 1;
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
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_WithOutObstacles uniquePaths = new DP_UniquePaths_WithOutObstacles();
System.out.println(uniquePaths.countUniquePaths(new int[3][3]));
}
}
```

- Output

```
6
```

- 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