Simple | Easy to understand | Though Process| Explanation | 4 Solutions | UniquePath I extension
This question is extension of Unique Path I; \nUnique path 1 solution [https://leetcode.com/problems/unique-paths/discuss/374561/100-or-5-Solutions-or-Step-by-S
This question is extension of Unique Path I; \nUnique path 1 solution [https://leetcode.com/problems/unique-paths/discuss/374561/100-or-5-Solutions-or-Step-by-Step-optimisation-or-Dp-thought-process] \n\nI just extends all the solution presented above here with minimal changes\n\n**Backtracking**\n\n```\n\n/**\n * We can solve this problem through backtracking.\n * Backtracking\n * 1. Our goal: To reach destination cell (m-1,n-1), once reach it counted as one path\n * 2. Our constraints: a) We can not move outside of boundary b) we can\'t go through obstacles\n * 3. Our choices: a) we can move either Down (i+1,j) or right (i, j+1) from any cell\n * <p>\n * Complexity:\n * To reach a cell there are two way and we try all the source cell to reach this cell.\n * Complexity: O((m*n)^2) /O (m*n)\n * <p>\n * TLE\n */\nclass UniquePathsIIBacktracking {\n\n\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n\n        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0)\n            return 0;\n\n        int m = obstacleGrid.length;\n        int n = obstacleGrid[0].length;\n\n\n        final int sx = 0, sy = 0;\n        final int dx = m - 1, dy = n - 1;\n\n        return uniquePaths(obstacleGrid, m, n, sx, sy, dx, dy);\n\n    }\n\n    private int uniquePaths(int[][] maze, int m, int n, int sx, int sy, int dx, int dy) {\n\n        //1. Our goal: To reach destination cell (m-1,n-1), once reach it counted as one path\n        if (sx == dx && sy == dy)\n            return 1;\n\n        int path = 0;\n        if (isSafe(sx, sy, m, n, maze)) {\n\n            maze[sx][sy] = -1; //not available for next round\n\n            path = uniquePaths(maze, m, n, sx + 1, sy, dx, dy)  //down\n                    +\n                    uniquePaths(maze, m, n, sx, sy + 1, dx, dy);//right\n\n            maze[sx][sy] = 0; // available for next round\n        }\n        return path;\n    }\n\n    private boolean isSafe(int sx, int sy, int m, int n, int[][] maze) {\n        if (sx >= m || sy >= n || sx < 0 || sy < 0 || maze[sx][sy] == -1 || maze[sx][sy] == 1) //Line change from UniqPathsI\n            return false;\n        return true;\n    }\n\n\n}\n\n```\n\n**DP: Top Down; cache backtraking solutions**\n\n```\n\n/**\n * In above backtracking, we visit same cell[i][j] and try to reach destination[m-1][n-1].\n * This happen again n again for different source cell [sx][sy] for this cell [i][j].\n * <p>\n * Since there are overlapping sub-problems, we can cache them; Hence DP\n * <p>\n * dp[i][j] = dp[i+1][j] + dp[i][j+1] ; [i,j] is in range of [m,n]\n * *        = 0 [i,j] is Not in range of [m,n]\n * base case:\n * i==dx, j==dy => dp[i][j] = 1\n * <p>\n * dp[sx][sy] is output\n * <p>\n * <p>\n * <p>\n * Complexity : To reach a cell there are two way and we try them only once from the source cell to reach this cell.\n * O(m*n) / O (m*n)\n * <p>\n * Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths II.\n * Memory Usage: 40.6 MB, less than 30.77% of Java online submissions for Unique Paths II.\n */\nclass UniquePathIIDPTopDown {\n\n\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n\n        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0)\n            return 0;\n\n        int m = obstacleGrid.length;\n        int n = obstacleGrid[0].length;\n\n        int dp[][] = new int[m][n];\n        for (int i = 0; i < m; i++)\n            Arrays.fill(dp[i], -1);\n\n        final int sx = 0, sy = 0;\n        final int dx = m - 1, dy = n - 1;\n\n        return uniquePaths(obstacleGrid, dp, m, n, sx, sy, dx, dy);\n\n    }\n\n    private int uniquePaths(int[][] maze, int dp[][], int m, int n, int sx, int sy, int dx, int dy) {\n\n        if (isSafe(sx, sy, m, n, maze)) {\n\n            //1. Our goal: To reach destination cell (m-1,n-1), once reach it counted as one path\n            if (sx == dx && sy == dy)\n                return dp[sx][sy] = 1;\n\n            if (dp[sx][sy] != -1)\n                return dp[sx][sy];\n\n            return dp[sx][sy] =\n                    uniquePaths(maze, dp, m, n, sx + 1, sy, dx, dy)  //down\n                            +\n                            uniquePaths(maze, dp, m, n, sx, sy + 1, dx, dy);//right\n        }\n        return 0;\n    }\n\n    private boolean isSafe(int sx, int sy, int m, int n, int[][] maze) {\n        if (sx >= m || sy >= n || sx < 0 || sy < 0 || maze[sx][sy] == 1) //Line change from UniqPathsI\n            return false;\n        return true;\n    }\n}\n\n```\n\n**DP: Bottom up [2 variation ]**\n\n```\n\n/**\n * * dp[i][j] = dp[i-1][j] + dp[i][j-1] ; [i,j] is in range of [m,n]\n * * *        = 0 [i,j] is Not in range of [m,n]\n * * base case:\n * * i==0 or j==0 => dp[i][j] = 0\n * * i==dx, j==dy => dp[i][j] = 1\n * * <p>\n * * dp[dx][dy] is output\n * <p>\n * * Complexity : To reach a cell there are two way and we try them only once from the source cell to reach this cell.\n * * O(m*n) / O (m*n)\n * <p>\n * Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths II.\n * Memory Usage: 40.9 MB, less than 16.92% of Java online submissions for Unique Paths II.\n */\nclass UniquePathsIIDPBottomUp {\n\n\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0)\n            return 0;\n\n        int m = obstacleGrid.length;\n        int n = obstacleGrid[0].length;\n\n        final int dp[][] = new int[m][n];\n\n        if (obstacleGrid[0][0] == 1)\n            return 0;\n\n        for (int i = 0; i < m; i++) {\n\n\n            for (int j = 0; j < n; j++) {\n\n                /**\n                 * If this is obstacle , can\'t move from here to anywhere\n                 */\n                if (obstacleGrid[i][j] == 1)\n                    dp[i][j] = 0;\n                else if (i == 0 && j == 0) //if this is a source, then we can definitely reach here by 1 way\n                    dp[i][j] = 1;\n                else if (i == 0) //if this is first row, and moving right direction then we can do whatever we did on previous step\n                    dp[i][j] = dp[i][j - 1];\n                else if (j == 0) //if this is first col, and moving down direction then we can do whatever we did on previous step\n                    dp[i][j] = dp[i - 1][j];\n                else\n                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; //we can come here either down or right\n            }\n\n        }\n\n        return dp[m - 1][n - 1];\n    }\n\n\n    /**\n     * Build using pre-check base cases\n     *\n     * @param obstacleGrid\n     * @return\n     */\n    public int uniquePathsWithObstaclesLong(int[][] obstacleGrid) {\n        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0)\n            return 0;\n\n        int m = obstacleGrid.length;\n        int n = obstacleGrid[0].length;\n\n        final int dp[][] = new int[m][n];\n\n\n        for (int i = 0; i < m; i++)\n            if (obstacleGrid[i][0] != 1)\n                dp[i][0] = 1;\n            else\n                break;\n\n\n        for (int j = 0; j < n; j++)\n            if (obstacleGrid[0][j] != 1)\n                dp[0][j] = 1;\n            else\n                break;\n\n        for (int i = 1; i < m; i++) {\n\n            for (int j = 1; j < n; j++) {\n\n                if (obstacleGrid[i][j] != 1) {\n\n                    if (obstacleGrid[i - 1][j] != 1)\n                        dp[i][j] = dp[i - 1][j];\n\n                    if (obstacleGrid[i][j - 1] != 1)\n                        dp[i][j] += dp[i][j - 1];\n                }\n            }\n        }\n\n\n        return dp[m - 1][n - 1];\n\n\n    }\n\n}\n\n```\n\n**DP: Bottom up; Space optimized**\n\n```\n\n/**\n * * dp[i][j] = dp[i-1][j] + dp[i][j-1] ; [i,j] is in range of [m,n]\n * * *        = 0 [i,j] is Not in range of [m,n]\n * * base case:\n * * i==0 or j==0 => dp[i][j] = 0\n * * i==dx, j==dy => dp[i][j] = 1\n * * <p>\n * * dp[dx][dy] is output\n * <p>\n * We can see we are using only two rows at a time. We can optimize the space\n * dp[i-1][j] => dp[j] old\n * dp[i][j-1] => dp[j-1] old\n * <p>\n * Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths II.\n * Memory Usage: 39.6 MB, less than 58.46% of Java online submissions for Unique Paths II.\n */\nclass UniquePathsIIDPBottomUpSpaceOptimize {\n\n\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0)\n            return 0;\n\n        int m = obstacleGrid.length;\n        int n = obstacleGrid[0].length;\n\n        final int dp[] = new int[n];\n\n        if (obstacleGrid[0][0] == 1)\n            return 0;\n\n        for (int i = 0; i < m; i++) {\n\n\n            for (int j = 0; j < n; j++) {\n\n                /**\n                 * If this is obstacle , can\'t move from here to anywhere\n                 */\n                if (obstacleGrid[i][j] == 1)\n                    dp[j] = 0;\n                else if (i == 0 && j == 0) //if this is a source, then we can definitely reach here by 1 way\n                    dp[j] = 1;\n                else if (i == 0) //if this is first row, and moving right direction then we can do whatever we did on previous step\n                    dp[j] = dp[j - 1];\n                else if (j == 0) //if this is first col, and moving down direction then we can do whatever we did on previous step\n                    dp[j] = dp[j];\n                else\n                    dp[j] = dp[j] + dp[j - 1]; //we can come here either down or right\n            }\n\n        }\n\n        return dp[n - 1];\n    }\n\n\n}\n```\n\nRef: Unique path 1 solution [https://leetcode.com/problems/unique-paths/discuss/374561/100-or-5-Solutions-or-Step-by-Step-optimisation-or-Dp-thought-process]
['Dynamic Programming', 'Backtracking', 'Memoization']