[Python] Simple approach (DP approach explained in a super simple manner)
This problem is almost a spitting image of  62. Unique Paths.\n\nLet\'s think of this problem in a super simple manner.\n\nOne important thing to remember is yo
This problem is almost a spitting image of  [62. Unique Paths](https://leetcode.com/problems/unique-paths/).\n\nLet\'s think of this problem in a super simple manner.\n\nOne important thing to remember is you can only walk right and down.\nNotation I am going to use (row, column).\n\nFirst, I create a placeholder 2d array, called `arr_path`, with 0s.\n\nWe are going to walk over the cells (the two for loops in the code). And each time we step on a cell, we are going to ask a question to ourself, how many unique paths are there to get to this cell? Well, for the first cell (0,0) we would only have 1 unique path. So we will start off with that.\n\nNext, think of walking over cell (0,1). How many unique paths are there to get to this cell? Well, it is too simple since we can only have 1 unique path to get to (0,1) from (0,0). This behavior is same for all the cells in the topmost row.\n\nNow, we get to the second row, we ask the same qustion for the cell in (1,0). How many unique paths are there to get from (0,0)? This is too simple since there is only one path to get to (1,0) from (0,0). But now, when we get to (1,1), we have to add the unique path to get to (1,0) and unique path to get to (0,1), so there are 2 unique paths to get to (1,1) from (0,0).\n\nThat\'s all you gotta do. And whenever you step on the cell, you just need to sum up the unique path to get to the cell which is above your current cell and the unique path to get to the cell which is left of your current cell (both of which has been computed before). We are accumulating the unique paths of every grid cell as we walk over the grid.\n\nSo now, when you see an obstacle, simply skip upading `arr_path` for that cell. When you get to the next cell, you will look for previous cells (up and left) in `arr_path` and you will add up the paths. Since you skipped updating `arr_path` when you saw an obstacle, that value will remain 0 and you are just adding up 0 with whatever number the other previous cell has (it can be 0 too, if both of the previous cells are obstacles).\n\nFinally you just return the unique path which you get for the cell which is at the bottom-right corner! This can be 0 too if there is an obstacle there. Since `arr_path` is initialized with all 0s, if there is an obstacle in the final cell, you will just return 0.\n\nAnd, this basically is dynamic programming.\n\n```\nclass Solution:\n    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n        if len(obstacleGrid) == 0 or obstacleGrid is None or obstacleGrid[0][0] == 1: # All the edge cases, including the case where the starting position has obstacle\n            return 0\n        \n        rows = len(obstacleGrid)\n        cols = len(obstacleGrid[0])\n        arr_paths = [[0 for _ in range(cols)] for _ in range(rows)]\n        \n        for r in range(rows):\n            for c in range(cols):\n                if r == 0 and c == 0:\n                    arr_paths[r][c] = 1 # There is one way to get from starting position to starting position\n                    continue\n                    \n                if obstacleGrid[r][c] == 1: # obstacle, don\'t count\n                    continue\n                    \n                if r-1 < 0:  # For topmost row\n                    arr_paths[r][c] = arr_paths[r][c-1]\n                elif c-1 < 0: # For leftmost column\n                    arr_paths[r][c] = arr_paths[r-1][c] \n                else:\n                    arr_paths[r][c] = arr_paths[r][c-1] + arr_paths[r-1][c]\n                \n        return arr_paths[r][c] # Even if the ending position has obstacle, it will return 0 since the placeholder array is initialized with all 0s\n```
['Dynamic Programming', 'Python']