Python top down dp
\nclass Solution:\n    # top down dp\n    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n        m, n = len(obstacleGrid), len(obsta
```\nclass Solution:\n    # top down dp\n    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n        m, n = len(obstacleGrid), len(obstacleGrid[0])\n        \n        # memo for dp\n        memo = [[None for _ in range(n)] for __ in range(m)]\n        \n        # edge case\n        if obstacleGrid[0][0] == 1:\n            return 0\n        \n        # we want to fill first row and column with 0 if we find an obstacle from that point to the end of the row or column. This way we can return 0 to indicate that a path is not possible because an obstacle blocks it\n        row_fill = 1\n        col_fill = 1\n        for r in range(m):\n            if obstacleGrid[r][0] == 1:\n                row_fill = 0\n            obstacleGrid[r][0] = row_fill\n            \n        for c in range(1, n):\n            if obstacleGrid[0][c] == 1:\n                col_fill = 0\n            obstacleGrid[0][c] = col_fill\n\n        # recursive function for top down dp\n        def dp(r, c):\n            # if we first row or col we return 1 if there is no blocking path\n            if r == 0 or c == 0:\n                return obstacleGrid[r][c]\n            # if we reach an obstacle there is no possible path\n            elif obstacleGrid[r][c] == 1:\n                return 0\n            # update memo if not cached\n            if memo[r][c] is None:\n                memo[r][c] = dp(r, c-1) + dp(r-1, c)\n            return memo[r][c]\n    \n        return dp(m - 1, n - 1)\n```\n\nTime: O(m * n) we only need to visit each matrix entry once\nSpace: O(m * n) for memo array
['Dynamic Programming', 'Python']