Question

Formatted question description: https://leetcode.ca/all/63.html

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 10⁹.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Constraints:

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] is 0 or 1.

Algorithm

Use Dynamic Programming to solve, using a two-dimensional dp array with size (m+1) x (n+1), where dp[i][j] means reaching (i-1, j-1)

The number of different paths of the location, then the range of i and j that needs to be updated is [1, m] and [1, n]. The state transition equation is the same as the previous question, because each position can only be moved from its upper and left positions, so the current dp value is also updated by adding the upper and left dp values, as shown below Show:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

It can be seen here that the size of the initialized d p array is (m+1) x (n+1), which is for the handle edge case. When i or j is 0, subtracting 1 may be wrong. When a certain position is an obstacle, its dp value is 0, just skip the position directly. Here also need to initialize a certain value of the dp array so that it can accumulate normally. When the starting point is not an obstacle, its dp value should be 1, that is, dp[1][1] = 1, because it is updated from dp[0][1] + dp[1][0], so two Any one of them can be initialized to 1.

Since LeetCode updated the test case of this question later, the use of int type dp array will have an overflow error, so use long type array instead to avoid overflow

Code

public class Unique_Paths_II {

    class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {

            if (obstacleGrid == null) {
                return 0;
            }

            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;

            int[][] dp = new int[m+1][n+1];
            dp[0][1] = 1;

            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {

                    if (obstacleGrid[i-1][j-1] == 0) {
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                    // else, ==1, obstacle, skip and leave as 0
                }
            }

            return dp[m][n];
        }
    }
}

############

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; ++i) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; ++j) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

// OJ: https://leetcode.com/problems/unique-paths-ii/
// Time: O(MN)
// Space: O(N)
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int M = obstacleGrid.size(), N = obstacleGrid[0].size();
        vector<long> memo(N, 0);
        memo[N - 1] = 1;
        for (int i = M - 1; i >= 0; --i) {
            for (int j = N - 1; j >= 0; --j) {
                if (obstacleGrid[i][j] == 1) memo[j] = 0;
                else memo[j] += j == N - 1 ? 0 : memo[j + 1];
            }
        }
        return memo[0];
    }
};

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not obstacleGrid:
            return 0

        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * (n+1) for _ in range(m+1)]

        # dp[1][1] = dp[0][1] + dp[1][0]
        # so, set either dp[0][1]=1, or set dp[1][0]=1
        dp[0][1] = 1

        for i in range(1, m+1):
            for j in range(1, n+1):
                if obstacleGrid[i-1][j-1] == 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                # else, ==1, obstacle, skip and leave as 0

        return dp[m][n]

############

class Solution(object):
  def uniquePathsWithObstacles(self, grid):
    """
    :type obstacleGrid: List[List[int]]
    :rtype: int
    """
    if not grid:
      return 0
    if grid[0][0] == 1:
      return 0
    dp = [[0] * len(grid[0]) for _ in range(0, len(grid))]
    dp[0][0] = 1 if grid[0][0] == 0 else 0
    for i in range(1, len(grid)):
      if grid[i][0] == 0:
        dp[i][0] = 1
      else:
        break

    for j in range(1, len(grid[0])):
      if grid[0][j] == 0:
        dp[0][j] = 1
      else:
        break

    for i in range(1, len(grid)):
      for j in range(1, len(grid[0])):
        if grid[i][j] == 1:
          dp[i][j] = 0
        else:
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[-1][-1]

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	m, n := len(obstacleGrid), len(obstacleGrid[0])
	dp := make([][]int, m)
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
	}
	for i := 0; i < m && obstacleGrid[i][0] == 0; i++ {
		dp[i][0] = 1
	}
	for j := 0; j < n && obstacleGrid[0][j] == 0; j++ {
		dp[0][j] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if obstacleGrid[i][j] == 0 {
				dp[i][j] = dp[i-1][j] + dp[i][j-1]
			}
		}
	}
	return dp[m-1][n-1]
}

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    const dp = Array.from({ length: m }, () => new Array(n).fill(0));
    for (let i = 0; i < m; i++) {
        if (obstacleGrid[i][0] === 1) {
            break;
        }
        dp[i][0] = 1;
    }
    for (let i = 0; i < n; i++) {
        if (obstacleGrid[0][i] === 1) {
            break;
        }
        dp[0][i] = 1;
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                continue;
            }
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

impl Solution {
    pub fn unique_paths_with_obstacles(obstacle_grid: Vec<Vec<i32>>) -> i32 {
        let m = obstacle_grid.len();
        let n = obstacle_grid[0].len();
        if obstacle_grid[0][0] == 1 || obstacle_grid[m - 1][n - 1] == 1 {
            return 0;
        }
        let mut dp = vec![vec![0; n]; m];
        for i in 0..n {
            if obstacle_grid[0][i] == 1 {
                break;
            }
            dp[0][i] = 1;
        }
        for i in 0..m {
            if obstacle_grid[i][0] == 1 {
                break;
            }
            dp[i][0] = 1;
        }
        for i in 1..m {
            for j in 1..n {
                if obstacle_grid[i][j] == 1 {
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        dp[m - 1][n - 1]
    }
}

63 - Unique Paths II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions