[Python] DFS+DP explained solution
This solution is just a variation of the standard solution provided by leetcode, but I think it\'s easier to understand. So basically the map is a acyclic direc
This solution is just a variation of the standard solution provided by leetcode, but I think it\'s easier to understand. So basically the map is a acyclic directed graph, and we just need to find the total number of paths from start to end.\n\nNormally DFS is sufficient for this kind of problem, however since we only need to report a single number, we can record the number of paths starting from a cell *u* once we completed the DFS starting from *u*. Next time when we hit *u* again, we know exactly the DFS result starting from *u*, so we don\'t have to do it again.\n\nNote: `lru_cache`([doc](https://docs.python.org/3/library/functools.html?highlight=lru_cache#functools.lru_cache)) helps store the returned result of every distinct method call. It functions like a `dict` here, and you can also use a `dict` to do the same thing.\n```python\nfrom functools import lru_cache\nclass Solution:\n    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n        M, N = len(obstacleGrid), len(obstacleGrid[0])\n        \n        @lru_cache(maxsize=None)\n        def dfs(i, j):\n            if obstacleGrid[i][j]:      # hit an obstacle\n                return 0\n            if i == M-1 and j == N-1:   # reach the end\n                return 1\n            count = 0\n            if i < M-1:\n                count += dfs(i+1, j)    # go down\n            if j < N-1:\n                count += dfs(i, j+1)    # go right\n            return count\n        \n        return dfs(0, 0)\n```\nThe time and space complexity are both O(MN).\n\nVote up if you find this helpful, thanks!
['Dynamic Programming', 'Depth-First Search', 'Python', 'Python3']