LeetCode - Unique Paths II | Darren's Blog

Follow up for LeetCode - 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.

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

dp[i][j]={0dp[i−1][j]+dp[i][j−1]if grid[i][j]=1otherwise.

Then we can scan the grid in the row-major manner and update dp[i][j] accordingly. Finally,dp[m−1][n−1] is what we want. Since dp[i][j] depend on grid[i][j] and the two cells to its left and top, a whole table for dp is not necessary; an array of length n suffices (or of lengthm , depending on the implementation). To avoid boundary check, an array of length n+1 is used below.
O(n) Space, code from http://www.darrensunny.me/leetcode-unique-paths-ii/

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

        if (obstacleGrid == null || obstacleGrid.length == 0 ||

                obstacleGrid[0].length == 0)

            return 0;

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

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

        dp[1] = 1;      // Initialization: one unique path to the starting point

        // Compute the number of unique paths to obstacleGrid[i][j]

        // Normally, it equals to the sum of the number of unique paths to obstacleGrid[i][j-1]

        // and that to obstacleGrid[i-1][j], except the case when the cell contains obstacles

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (obstacleGrid[i][j] == 1)    // Obstacle

                    dp[j+1] = 0;    // Cannot reach a cell containing obstacle

                else        // Empty space

                    dp[j+1] += dp[j];

            }

        }

 

        return dp[n];

    }

Don't use extra space
Code from http://blog.csdn.net/kenden23/article/details/17317805

int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {

  int r = obstacleGrid.size();

  if (r < 1) return 1;

  int c = obstacleGrid[0].size();

  

  vector<int> table(c);

  

  if (obstacleGrid[0][0] == 1) return 0;

  else table[0] = 1;

  for (int i = 1; i < c && obstacleGrid[0][i] != 1; i++)

  {

   table[i] = 1;

  }



  for (int i = 1; i < r; i++)

  {

   //注意：如果是只有单列的时候,每列需要初始化

   //注意：不等于1的时候是填回上一列的值，并非初始化为1

   if (obstacleGrid[i][0] == 1) table[0] = 0;



   for (int j = 1; j < c; j++)

   {

    if (obstacleGrid[i][j] != 1)

     table[j] += table[j-1];

    else table[j] = 0;

   }

  }

  return table[c-1];

 }

O(m*N) space: Code from http://yucoding.blogspot.com/2013/04/leetcode-question-117-unique-path-ii.html

int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        int m = obstacleGrid.size();

        int n = obstacleGrid[0].size();

         

        vector<vector<int> > arr(m,vector<int>(n,0));

         

        if (obstacleGrid[0][0]==1){return 0;}

        arr[0][0]=1;

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

            if (obstacleGrid[i][0]!=1){

                arr[i][0] = arr[i-1][0];

            }

        }

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

            if (obstacleGrid[0][i]!=1){

                arr[0][i] = arr[0][i-1];

            }

        }

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

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

                if (obstacleGrid[i][j]!=1){

                    arr[i][j] = arr[i][j-1] + arr[i-1][j];

                }

            }

        }  

        return arr[m-1][n-1];

    }

Read full article from LeetCode - Unique Paths II | Darren's Blog