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));
    }
}
Follow HelloKoding