63

63. Unique Paths II (Medium)

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 * 109.

 

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.

Companies: Atlassian, Cruise Automation, athenahealth

Related Topics:
Array, Dynamic Programming, Matrix

Similar Questions:

• Unique Paths (Medium)
• Unique Paths III (Hard)
• Minimum Path Cost in a Grid (Medium)
• Paths in Matrix Whose Sum Is Divisible by K (Hard)

Solution 1. DP

Let dp[i+1][j+1] be the number of ways to reach A[i][j]. The answer is dp[M][N].

dp[1][1] = 1

dp[i+1][j+1] = 0                         // if A[i][j] == 1
               dp[i][j+1] + dp[i+1][j]   // if A[i][j] == 0

Since dp[i+1][j+1] only depends on dp[i][j+1] and dp[i+1][j], we can reduce the space complexity from O(MN) to O(N).

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