Finding Unique Paths in a Grid with Obstacles: A Dynamic Programming Approach
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires us to find the number of unique paths from the top-left corner of 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires us to find the number of unique paths from the top-left corner of a matrix to the bottom-right corner. The matrix contains obstacles which are represented by 1 and free spaces represented by 0. If there is an obstacle at a cell, we cannot go through that cell. Our intuition should be to use Dynamic Programming (DP) to solve this problem.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can use a DP matrix `dp` of the same size as the input `obstacleGrid`. The value of `dp[i][j]` represents the number of unique paths to reach the cell at `(i, j)` in `obstacleGrid`.\n\nWe can initialize the `dp` matrix with `0`s. For the top-left corner of `obstacleGrid`, if there is an obstacle, then there are no unique paths to reach that cell. Hence, we set `dp[0][0]` to `0`. Otherwise, there is only one unique path to reach that cell, so we set `dp[0][0]` to `1`.\n\nNext, we can consider the first row and first column of `obstacleGrid`. If there is an obstacle in any cell in the first row or first column, we cannot move right or down, respectively. Hence, we set the corresponding `dp` value to `0`. Otherwise, we can only move either right or down in these cells, and hence there is only one unique path to reach these cells. We set the corresponding `dp` value to `1`.\n\nWe then iterate over the remaining cells in `obstacleGrid`, and for each cell, we check if there is an obstacle in that cell. If there is an obstacle, we set the corresponding dp value to 0, as we cannot go through that cell. Otherwise, the number of unique paths to reach that cell is the sum of the number of unique paths to reach the cell above it and the cell to the left of it. Hence, we set `dp[i][j] = dp[i-1][j] + dp[i][j-1]`.\n\nFinally, the number of unique paths to reach the bottom-right corner of `obstacleGrid` is `dp[m-1][n-1]`, where `m` and `n` are the number of rows and columns in `obstacleGrid`, respectively.\n# Complexity\n- Time complexity:  The algorithm iterates over each cell in `obstacleGrid` exactly once, and for each cell, it performs a constant number of operations. Hence, the time complexity of this algorithm is $$O(mn)$$.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: The algorithm uses a DP matrix `dp` of size `m` x `n`, which requires $$O(mn)$$ space.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n        m, n = len(obstacleGrid), len(obstacleGrid[0])\n        dp = [[0] * n for _ in range(m)]\n        dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0\n        for i in range(1, m):\n            if obstacleGrid[i][0] == 0:\n                dp[i][0] = dp[i-1][0]\n        for j in range(1, n):\n            if obstacleGrid[0][j] == 0:\n                dp[0][j] = dp[0][j-1]\n        for i in range(1, m):\n            for j in range(1, n):\n                if obstacleGrid[i][j] == 0:\n                    dp[i][j] = dp[i-1][j] + dp[i][j-1]\n        return dp[m-1][n-1]\n```
['Array', 'Dynamic Programming', 'Matrix', 'Python3']