63. Unique Paths II

#dp

Problem

Unique Paths II - LeetCodeLeetCode

Intuition

It follows the same approach as 62. Finding Unique Path. The only thing is it has an extra constraint where you could be blocked from exploring in few cells.

Solution

class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];

        return tabulationHelper(grid, dp);
    }

    /**
     * Calculates the number of unique paths using a tabulation (bottom-up) approach.
     */
    private int tabulationHelper(int[][] grid, int[][] dp) {
        if(grid[0][0] == 1) {
            return 0;
        }

        dp[0][0] = 1;
        int R = grid.length, C = grid[0].length;

        // Calculate the number of paths for the first column
        for(int row = 1; row < R; row++) {
            // Before we update the current dp cell, we need to check if the 
            // current cell of grid is accessible and also check if the previous 
            // cell is accessible. If the previous cell is not accessible then
            // the move cannot be made to current cell.
            if(grid[row][0] == 0 && dp[row-1][0] == 1) {
                dp[row][0] = 1;
            }
        }

        // Calculate the number of paths for the first row
        for(int col = 1; col < C; col++) {
            if(grid[0][col] == 0 && dp[0][col-1] == 1) {
                dp[0][col] = 1;
            }
        }

        // Calculate the number of paths for the remaining cells
        for(int row = 1; row < R; row++) {
            for(int col = 1; col < C; col++) {
                if(grid[row][col] == 0) {
                    int up = dp[row-1][col];
                    int left = dp[row][col-1];
                    dp[row][col] = up + left;
                }
            }
        }
        return dp[R-1][C-1];
    }

    /**
     * Calculates the number of unique paths using a memoization (top-down) approach.
     * This function is not used in this code.
     */
    private int memoizationHelper(int i, int j, int[][] grid, int[][] dp) {
        // If we go out of bounds or encounter an obstacle, return 0 as there are no paths.
        if(i < 0 || j < 0 || grid[i][j] == 1) {
            return 0;
        }

        // If we reach the top-left corner, return 1 as we have found a unique path.
        if(i == 0 && j == 0) {
            return 1;
        }

        // If the result for the current position is already computed, return it.
        if(dp[i][j] != 0) {
            return dp[i][j];
        }

        // Calculate the number of paths by recursively moving either up or left.
        int up = recursiveHelper(i-1, j, grid);
        int left = recursiveHelper(i, j-1, grid);

        // Store the computed result in the dp array and return it.
        return dp[i][j] = up + left;
    }

    /**
     * Calculates the number of unique paths using a recursive approach.
     */
    private int recursiveHelper(int i, int j, int[][] grid) {
        // If we reach the top-left corner, return 1 as we have found a unique path.
        if(i == 0 && j == 0) {
            return 1;
        }

        // If we go out of bounds or encounter an obstacle, return 0 as there are no paths.
        if(i < 0 || j < 0 || grid[i][j] == 1) {
            return 0;
        }

        // Calculate the number of paths by recursively moving either up or left.
        int up = recursiveHelper(i-1, j, grid);
        int left = recursiveHelper(i, j-1, grid);

        // Return the sum of paths from the current position.
        return up + left;
    }
}