Share my Java solution: O(m*n) time complexity, no extra space.
Obviously, this is a DP problem.\n\nLet F(i,j) denotes the paths from top left to cell (i,j).\n\n\nIf cell (i,j) has an obstacle, then F(i,j) = 0.\nelse \n\n\nf
Obviously, this is a DP problem.\n\nLet F(i,j) denotes the paths from top left to cell (i,j).\n\n\nIf cell (i,j) has an obstacle, then F(i,j) = 0.\nelse \n\n\nfor j>0, F(0,j) = F(0,j-1)\n   \n\nfor i>0, F(i,0) = F(i-1,0)\n    \n\nfor i>0&&j>0, F(i,j) = F(i-1,j)+F(i,j-1)\n\nWe can take advantage of the obstacle array without using extra space.         \n\n        if(obstacleGrid==null||obstacleGrid.length==0)\n        \treturn 0;\n\n        for(int i=0;i<obstacleGrid.length;i++)\n        \tfor(int j=0;j<obstacleGrid[0].length;j++)\n        \t{\n        \t\tif(i==0)\n        \t\t{\n        \t\t\tif(j==0)\n        \t\t\t\tobstacleGrid[0][0] = 1 - obstacleGrid[0][0];\n        \t\t\telse\n        \t\t\t\tobstacleGrid[0][j] = obstacleGrid[0][j]==1?0:obstacleGrid[0][j-1];\n        \t\t}\n        \t\telse \n        \t\t{\n        \t\t\tif(j==0)\n        \t\t\t\tobstacleGrid[i][0] = obstacleGrid[i][0]==1?0:obstacleGrid[i-1][0];\n        \t\t\telse \n        \t\t\t\tobstacleGrid[i][j] = obstacleGrid[i][j]==1?0:(obstacleGrid[i-1][j]+obstacleGrid[i][j-1]);\n\t\t\t\t}\n        \t}\n        return obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1];
[]