Java - 0ms beats 100% - recursion top down DP
Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths II.\nMemory Usage: 38.2 MB, less than 55.04% of Java online submissions for Uniqu
Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths II.\nMemory Usage: 38.2 MB, less than 55.04% of Java online submissions for Unique Paths II.\n\n```\nclass Solution {\n        \n    private int util(int[][] b, int x, int y, int[][] dp)\n    {\n        //base case check - if x or y is invalid or if there is obstacle\n        if( x < 0 || y < 0 || b[x][y] == 1)\n            return 0;\n        \n        // if we reached the cell (0,0) - return 1 as there is a path\n        if(x == 0  && y == 0 )\n            return 1;\n        \n\t// check your cache to avoid repeated check\n        if(dp[x][y] != Integer.MAX_VALUE)\n            return dp[x][y];\n\n\t// else go to the top or left cell and store back the result        \n        dp[x][y] = util(b, x-1, y, dp) + util(b, x, y-1, dp);\n        \n        return dp[x][y];\n        \n    }\n    \n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n       //base case\n        if(obstacleGrid.length == 0)\n            return 0;\n        \n        if(obstacleGrid.length == 1 && obstacleGrid[0].length ==1)\n            return obstacleGrid[0][0] == 0 ? 1 : 0;\n        \n        int[][] dp  = new int[obstacleGrid.length][obstacleGrid[0].length];\n        \n\t// initialize DP array\n        for(int i=0; i < dp.length; i++)\n            Arrays.fill(dp[i], Integer.MAX_VALUE );\n        \n        //start from the last for this question\n        int m = obstacleGrid.length -1 ;\n        int n = obstacleGrid[0].length -1;\n        \n       // Start from the bottom right most cell and go till (0,0) cell\n        util(obstacleGrid, m, n, dp);\n        \n        return dp[m][n] != Integer.MAX_VALUE ? dp[m][n] : 0; \n    }\n}\n```
[]