Question

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

63	Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.

Note: m and n will be at most 100.

@tag-array

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

Java

  • 
    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];
            }
        }
    }
    
  • // 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(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]
    
    

All Problems

All Solutions