My C++ Dp solution , very simple!


  • 58
    K

    just use dp to find the answer , if there is a obstacle at (i,j), then dp[i][j] = 0.
    time is O(nm) , space is O(nm) .
    here is my code:

    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
            int m = obstacleGrid.size() , n = obstacleGrid[0].size();
            vector<vector<int>> dp(m+1,vector<int>(n+1,0));
            dp[0][1] = 1;
            for(int i = 1 ; i <= m ; ++i)
                for(int j = 1 ; j <= n ; ++j)
                    if(!obstacleGrid[i-1][j-1])
                        dp[i][j] = dp[i-1][j]+dp[i][j-1];
            return dp[m][n];
        }
    };

  • 0
    I

    You don't need extra space .


  • 0
    U

    elegant code! could you explain why it is "if(!obstacleGrid[i-1][j-1])" but not "if(!obstacleGrid[i][j])"


  • 1
    P

    Here is my solution using O(n) space :)

    class Solution {
        public:
            int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
                int m = obstacleGrid.size();
                int n = obstacleGrid[0].size();
                if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1)
                    return 0;
                
                int res[n];
                res[n-1] = 1;
                for(int i = n-2; i >= 0; --i){
                    if(obstacleGrid[m-1][i] == 1)
                        res[i] = 0;
                    else
                        res[i] = res[i+1];
                }
                
                for(int i = m-2; i >= 0; --i){
                    for(int j = n-1; j >=0; --j){
                        if(j == n-1){
                            if(obstacleGrid[i][j] == 1)
                                res[j] = 0;
                        }else{
                            if(obstacleGrid[i][j] == 1)
                                res[j] = 0;
                            else
                                res[j] += res[j+1];
                        }
                    }
                }
                return res[0];
            }
        };

  • 0
    J

    because obstacleGrid size is m*n, but dp is (m+1) * (n+1)


  • 3
    W
    class Solution {
    

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

        int row=obstacleGrid.size();
        int col=obstacleGrid[0].size();
        vector<vector<int>> k(row,vector<int>(col,0));
        
        
        if(obstacleGrid[0][0]==1||obstacleGrid[row-1][col-1]==1)
        return 0;
        else
        k[0][0]=1;
        
        
        for(int i=1;i<row;++i)
        if(!obstacleGrid[i][0])
        k[i][0]=k[i-1][0];
        
        
        for(int j=1;j<col;++j)
        if(!obstacleGrid[0][j])
        k[0][j]=k[0][j-1];
        
        
        for(int i=1;i<row;++i)
        for(int j=1;j<col;++j)
        {
                if(!obstacleGrid[i][j])
                k[i][j]=k[i-1][j]+k[i][j-1];
                
                
                
        }
        return k[row-1][col-1];
      
      
      
      
      
      
      
      
      
      
    }
    

    };


  • 7

    Nice pre-processing dp[0][1] = 1; to make the code so simple!


  • 0
    E

    But why did u make it one??


  • 0
    E

    Your have to initialise the entry point for the first time.(your for loop is begin with(1,1))


  • 2
    S

    Without extra space: (I can combine all three loop into one, but I don't wanna have too much condition checking.)

    public class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int m = obstacleGrid.length, n = obstacleGrid[0].length;
            
            //flip upper left cell (the start cell): 1 => 0 or 0 => 1
            obstacleGrid[0][0] ^= 1;
            
            //first row: if 1, then 0; otherwise, left cell
            for(int i = 1; i < n; i++)
                obstacleGrid[0][i] = obstacleGrid[0][i] == 1 ? 0 : obstacleGrid[0][i - 1];
            
            //first column: if 1, then 0; otherwise, top cell
            for(int i = 1; i < m; i++)
                obstacleGrid[i][0] = obstacleGrid[i][0] == 1 ? 0 : obstacleGrid[i - 1][0];
                
            //rest: if 1, then 0; otherwise, left cell + top cell
            for(int i = 1; i < m; i++)
                for(int j = 1; j < n; j++)
                    obstacleGrid[i][j] = obstacleGrid[i][j] == 1 ? 0 : obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                    
            //return lower right cell (the end cell)
            return obstacleGrid[m - 1][n - 1];
        }
    }

  • 0
    W
    This post is deleted!

  • 4
    C

    More concise and O(n) space:

    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
            int m = (int)obstacleGrid.size(), n = obstacleGrid[0].size();
            vector<int> temp(m + 1, 0);
            temp[m-1] = 1;
            for (int j = n - 1; j >= 0; j--) {
                for (int i = m - 1; i >= 0; i--) {
                    if (obstacleGrid[i][j]) temp[i] = 0;
                    else temp[i] += temp[i+1];
                }
            }
            return temp[0];
        }
    };

  • 1
    H
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
            int m=obstacleGrid.size();
            int n=obstacleGrid[0].size();
            vector<int> dp(n+1,0);
            dp[1]=1;
            for(int i=0;i<m;i++){
                for(int j=1;j<=n;j++){
                    if(obstacleGrid[i][j-1]) dp[j]=0;
                    else dp[j]=dp[j]+dp[j-1];
                }
            }
            return dp[n];
        }
    

  • 0
    M

    @SpicyDog But you changed argument.Argument original is referenced parameter.


  • 0
    S

    i used it, but got run-time error when submit, can anyone help me?
    here is code

        int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int m = obstacleGrid.size() , n = obstacleGrid[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        dp[0][1] = 1;
        for(int i = 1 ; i <= m ; ++i)
            for(int j = 1 ; j <= n ; ++j)
                if(!obstacleGrid[i-1][j-1])
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
        return dp[m][n];
    }

  • 0
    S

    @sutongkui i got it, use long int instead of int


  • 0
    Z

    @sutongkui I got a reply from leetcode admin.
    They've just updated their C++ compiler settings to detect integer overflow(which would usually be just ignored and wrapped around).

    So the runtime error is caused by integer overflow.
    Reference:
    http://en.cppreference.com/w/cpp/error/overflow_error


  • 0
    D

    @sutongkui
    you'd better add the {} for every for loop and if statement.


  • 0
    0

    @uestc-ym becasue the element in obstacleGrid with index of[i-1,j-1] map to the dp's[i,j]
    NOTICE: vector's index starts from 0.


  • 0
    Q
    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {
            vector<int>v(obstacleGrid[0].size(),0);
            for(int i = 0 ; i < obstacleGrid[0].size() ; ++i){
                if( obstacleGrid[0][i] == 1 )break;
                v[i] = 1;
            }
            for(int i = 1 ; i < obstacleGrid.size() ; ++i){
                for(int j = 0 ; j < obstacleGrid[0].size() ; ++j){
                    if( obstacleGrid[i][j] == 1 )
                        v[j] = 0;
                    else v[j] = (j == 0) ?  v[j] : v[j] + v[j-1];
                }
            }
            return v[v.size()-1];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.