Python - Memo + DP Table - Explained
Code is fully commented, if you have any questions feel free.\n\nMemo version (better than 90% submissions)\n\n\nclass Solution:\n    def uniquePathsWithObstacl
Code is fully commented, if you have any questions feel free.\n\n***Memo version (better than 90% submissions)***\n\n```\nclass Solution:\n    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n        self.height, self.width = len(obstacleGrid), len(obstacleGrid[0])\n        self.memo = defaultdict(int)\n        \n        def walk(i, j):\n            # If were on an obstacle\n            if obstacleGrid[i][j] == 1: return 0\n            \n            # If we arrived to the end we know there is a path\n            if i == self.height - 1 and j == self.width - 1:\n                return 1\n            \n            # Memo\n            if (i, j) in self.memo:\n                return self.memo[(i, j)]\n            \n            # Travel down\n            if i < self.height - 1:\n                self.memo[(i, j)] += walk(i + 1, j)\n            \n            # Travel right\n            if j < self.width - 1:\n                self.memo[(i, j)] += walk(i, j + 1)\n            \n            return self.memo[(i, j)]\n                \n        \n        return walk(0, 0)\n```\n\n\n***Tabulated version (better than 85%)***\n\n```\nclass Solution:\n    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n        height, width = len(obstacleGrid), len(obstacleGrid[0])\n        if obstacleGrid[height - 1][width - 1] == 1: return 0\n        \n        dp = [[0 for _ in range(width + 1)] for _ in range(height + 1)]\n        dp[height - 1][width - 1] = 1\n        \n        for i in range(height)[::-1]:\n            for j in range(width)[::-1]:\n                # This if block skips the first iteration only\n                if i == height - 1 and j == width - 1: continue\n                if obstacleGrid[i][j] == 1: continue\n                dp[i][j] = dp[i + 1][j] + dp[i][j + 1]\n        \n        return dp[0][0]\n```
[]