JS, Python, Java, C++ | Easy DP Solution w/ Explanation
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\n#### Idea:\n
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nThe naive approach here would be to try every path with a **recursive** **depth first search** (**DFS**) approach. That would involve duplicating the processing used for repeating subpaths, however, which would quickly lead to a **TLE** result. When faced with repeating subproblems, we should be thinking of a **dynamic programming** (**DP**) approach to store completed subproblem and avoid any unnecessary duplication of processing.\n\nIn this situation, we can create a DP matrix (**dp**) in the same dimensions as our input matrix (**OG**). (_**Note**: We can choose to use an **in-place** approach here and use **OG** as our DP matrix in order to reduce the **space complexity** of our solution to **O(1)**._) Each cell in **dp** will represent the number of paths that lead to the corresponding cell in **OG**. Since the robot can only move either to the right or down, we can perform a **bottom-up** DP solution, working from the initial cell and iterating downward and rightward through **OG**.\n\nEach cell in **OG** (**OG[i][j]**) can potentially reached by only two previously-visited cells (**OG[i-1][j]** & **OG[i][j-1]**), so the number of ways to reach the current cell (**dp[i][j]**) should be the sum of the ways to reach those other two cells (**dp[i-1][j] + dp[i][j-1]**), should they exist.\n\nSince any cell representing an obstacle cannot be a part of a path, its value in **dp** should be **0**. We\'ll also need to seed the initial starting position with a value of **1** to represent the single initial path. Once we\'re done building **dp**, the value of the bottom-right cell should be our answer.\n\n - _**Time Complexity: O(N * M)** where **N** and **M** are the dimensions of the input matrix_\n - _**Space Complexity: O(N * M)** for the DP matrix_\n    - _or **O(1)** if we use an **in-place** approach for the DP matrix_\n\n---\n\n#### ***Implementation:***\n\nPython can opt to use @lru_cache instead of a standard DP matrix; the standard approach is shown below.\n\n---\n\n#### ***Javascript Code:***\n\nThe best result for the code below is **68ms / 38.6MB** (beats 100% / 96%).\n```javascript\nvar uniquePathsWithObstacles = function(OG) {\n    if (OG[0][0]) return 0\n    let m = OG.length, n = OG[0].length\n    let dp = Array.from({length: m}, el => new Uint32Array(n))\n    dp[0][0] = 1\n    for (let i = 0; i < m; i++)\n        for (let j = 0; j < n; j++)\n            if (OG[i][j] || (!i && !j)) continue\n            else dp[i][j] = (i ? dp[i-1][j] : 0) + (j ? dp[i][j-1] : 0)\n    return dp[m-1][n-1]\n};\n```\n\n---\n\n#### ***Python Code:***\n\nThe best result for the code below is **36ms / 14.2MB** (beats 94% / 84%).\n```python\nclass Solution:\n    def uniquePathsWithObstacles(self, OG: List[List[int]]) -> int:\n        if OG[0][0]: return 0\n        m, n = len(OG), len(OG[0])\n        dp = [[0] * n for _ in range(m)]\n        dp[0][0] = 1\n        for i in range(m):\n            for j in range(n):\n                if OG[i][j] or (i == 0 and j == 0): continue\n                dp[i][j] = (dp[i-1][j] if i else 0) + (dp[i][j-1] if j else 0)\n        return dp[m-1][n-1]\n```\n\n---\n\n#### ***Java Code:***\n\nThe best result for the code below is **0ms / 38.0MB** (beats 100% / 67%).\n```java\nclass Solution {\n    public int uniquePathsWithObstacles(int[][] OG) {\n        if (OG[0][0] == 1) return 0;\n        int m = OG.length, n = OG[0].length;\n        int[][] dp = new int[m][n];\n        dp[0][0] = 1;\n        for (int i = 0; i < m; i++)\n            for (int j = 0; j < n; j++)\n                if (OG[i][j] == 1 || (i == 0 && j == 0)) continue;\n                else dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);\n        return dp[m-1][n-1];\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n\nThe best result for the code below is **0ms / 7.7MB** (beats 100% / 46%).\n```c++\nclass Solution {\npublic:\n    int uniquePathsWithObstacles(vector<vector<int>>& OG) {\n        if (OG[0][0] == 1) return 0;\n        int m = OG.size(), n = OG[0].size();\n        vector<vector<int>> dp(m, vector<int>(n,0));\n        dp[0][0] = 1;\n        for (int i = 0; i < m; i++)\n            for (int j = 0; j < n; j++)\n                if (OG[i][j] == 1 || (i == 0 && j == 0)) continue;\n                else dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);\n        return dp[m-1][n-1];\n    }\n};\n```
['C', 'Python', 'Java', 'JavaScript']