Question:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

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.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [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

Thinking:

  • Method:
    • 还是通过dp，当前值为左侧和上侧的值的和。
    • 在初始化时，我们必须要判断是否valid，如果不是valid则不继续初始化下侧和右侧的值（保持默认值0）。
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid == null || obstacleGrid.length == 0)
            return 0;
        int height = obstacleGrid.length;
        int width = obstacleGrid[0].length;
        int[][] dp = new int[height][width];
        for(int i = 0; i < width; i++){
            if(isValid(obstacleGrid, 0, i))
                dp[0][i] = 1;
            else
                break;
        }
        for(int i = 0; i < height; i++){
            if(isValid(obstacleGrid, i, 0))
                dp[i][0] = 1;
            else
                break;
        }
        for(int i = 1; i < height; i++){
            for(int j = 1; j < width; j++){
                if(isValid(obstacleGrid, i, j)){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[height - 1][width - 1];
    }
    private static boolean isValid(int[][] ob, int row, int col){
        return ob[row][col] == 0;
    }
}

二刷

和上一道题解法是一样的，只是在解空间中需要加一个小判断。

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