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