Lintcode: 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.

Have you met this question in a real interview? 

Yes

Example

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.

Tags Expand 

Dynamic Programming Array

http://www.lintcode.com/en/problem/unique-paths/#

My Unique Path solution

DP:
1. dp(x, y) ---- how many ways for point go from (0, 0) to (x, y)
2. if(Rout(x, y) == 1) dp(x, y) = 0;
    else dp(x, y) = dp(x - 1, y) + dp(x, y - 1)
3. initial state: dp(0, 0) = 1;
    when x = 0: if no obstacle dp(0, y) = dp(0, y -1) else 0;
   when y = 0: if no obstacle dp(x, 0) = dp(x - 1, 0) else 0;

Time: O(m*n)
Space: O(mn) -- can be optimized
Format will be better if seperate situations when x = 0 and y = 0 into two another loops
reference: http://yucoding.blogspot.com/2013/04/leetcode-question-117-unique-path-ii.html

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution { public: /** * @param obstacleGrid: A list of lists of integers * @return: An integer */ int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { // write your code here if(obstacleGrid.size() == 0) return 0; int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<vector<int> > DP(m, vector<int>(n, 0)); for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(obstacleGrid[i][j] == 1) DP[i][j] = 0; else { int left, up; if(i == 0 && j == 0) { DP[i][j] = 1; continue; } if(i == 0) left = 0; else left = DP[i - 1][j]; if(j == 0) up = 0; else up = DP[i][j - 1]; DP[i][j] = left + up; } } } return DP[m - 1][n - 1]; } };

Lintcode second:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { public: /** * @param obstacleGrid: A list of lists of integers * @return: An integer */ int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { // write your code here //dp[i][j] //dp[i][j] = dp[i-1][j] + dp[i][j-1]; //intial status: dp[0][0] = 1, dp[i][0]/dp[0][j] = 1; //dp[obstacle] = 0; if(obstacleGrid.size() == 0) return 0; int row = obstacleGrid.size(); int col = obstacleGrid[0].size(); vector<vector<int> > dp(row, vector<int>(col)); if(obstacleGrid[0][0] == 1) return 0; dp[0][0] = 1; for(int i = 1; i < row; i++){ if(obstacleGrid[i][0]) dp[i][0] = 0; else dp[i][0] = dp[i-1][0]; } for(int j = 1; j < col; j++){ if(obstacleGrid[0][j]) dp[0][j] = 0; else dp[0][j] = dp[0][j-1]; } for(int i = 1; i < row; i++){ for(int j = 1; j < col; j++){ if(obstacleGrid[i][j]) dp[i][j] = 0; else dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[row - 1][col - 1]; } };