# HelloKoding

Practical coding guides

# Unique Paths Problems

In this article, you will learn to analyze and resolve to Unique paths without or with obstacles problems by using Dynamic programming algorithm

## Problem 1: Count unique paths without obstacles

• 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 1

• Input `A[3][3]` with values `{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}`
• Expected output `6`

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

DP_UniquePaths_WithOutObstacles.java

``````package com.hellokoding.algorithm;

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]));
}
}
``````

## Problem 2: Count unique paths with obstacles

• 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 2

• 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`

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

DP_UniquePaths_Obstacles.java

``````package com.hellokoding.algorithm;

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));
}
}
``````