[Java] time O(n*m), space O(1) + explanation
Let\'s say we have the following field with obstacles:\n\n\nLet\'s go through every cell and calculate how many paths are there to this cell.\nFirst cell: we ju
Let\'s say we have the following field with obstacles:\n![image](https://assets.leetcode.com/users/olsh/image_1542205389.png)\n\nLet\'s go through every cell and calculate how many paths are there to this cell.\nFirst cell: we just stept into it. That\'s all => only one path.\n![image](https://assets.leetcode.com/users/olsh/image_1542205778.png)\nGo to neighbor cells. One of them is obstacle. We mark it as 0 because in future, for calculating numbers or routes to other cells, they won\'t add anything.\nAnother cell is 1 because we can get there only from the first cell. \n![image](https://assets.leetcode.com/users/olsh/image_1542207602.png)\nEvery other cell (i,j) will be sum of cells above (i-1,j) and left (i,j-1). For border cells (with indices (ai,0) and (0, bi)) we assume that one of neighbor cells is 0, so just copy number from other cell:\n![image](https://assets.leetcode.com/users/olsh/image_1542208046.png)\n\nAfter it, we just get the number in the target cell.\n\nHere is the code:\n```\nclass Solution {\n           public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n           for (int i=0;i<obstacleGrid.length;i++){\n               for (int j=0;j<obstacleGrid[i].length;j++){\n                   if (obstacleGrid[i][j]==1) obstacleGrid[i][j]=0;\n                   else if (i==0 && j==0) obstacleGrid[i][j]=1;\n                   else if (i==0) obstacleGrid[i][j]=obstacleGrid[i][j-1];\n                   else if (j==0) obstacleGrid[i][j]=obstacleGrid[i-1][j];\n                   else obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];\n               }\n           }\n        return obstacleGrid[obstacleGrid.length-1][obstacleGrid[obstacleGrid.length-1].length-1];\n    }\n\n}\n\n```\n\nCurrently, I\'m searching for the ways to optimize it. For example if you meet an abstacle, you don\'t calculate all the cells "behind" it.
[]