Dp Solution for the Problem with 100% beats
Intuition\n Describe your first thoughts on how to solve this problem. \n#### We need to move from (0,0) to (m-1,n-1) so we have 4 direction of moves. explore a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n#### **We need to move from (0,0) to (m-1,n-1) so we have 4 direction of moves. explore all the moves when ever 1 is found decrement by 1 if health is less than 0 return back explore another path**\n\n### ****\n**using recursion and map to avoid the repeated steps******\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n-**>explore all the 4 paths from the each cell\n->if health less than 0 then stop\n->use the map to keep track already explored if already explored return the value else find and keep the value in map**\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nLet \n\uD835\uDC5A\nm be the number of rows and \n\uD835\uDC5B\nn be the number of columns in the grid.\n\nRecursive Calls:\n\nThe function solve explores all four possible directions (down, right, up, left) from each cell, which can lead to exponential growth in the number of calls.\nWithout memoization, the time complexity would be \n\uD835\uDC42(4\uD835\uDC5A\uD835\uDC5B)\nO(4mn)\n since each cell could theoretically result in 4 recursive calls (except at the borders).\nHowever, the memoization ensures that once a state (defined by the current position and health) is computed, it is stored and reused. There are \n\uD835\uDC5A\uD835\uDC5B\nmn cells, and for each cell, there can be at most \n\uD835\uDC3B\nH different health values (depending on how much health is left), where \n\uD835\uDC3B\nH is the initial health value.\nTherefore, the total number of unique states is at most \n\uD835\uDC42(\uD835\uDC5A\xD7\uD835\uDC5B\xD7\uD835\uDC3B)\nO(m\xD7n\xD7H), and memoization ensures that each state is computed only once.\n\nOperations per State:\n\nFor each state, the recursive function performs a constant amount of work (checking conditions and updating the memoization table).\nThus, the overall time complexity is \n\uD835\uDC42(\uD835\uDC5A\xD7\uD835\uDC5B\xD7\uD835\uDC3B)\nO(m\xD7n\xD7H).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n# ****Space Complexity:\n# **Recursive Stack:\n\nIn the worst case, the recursion depth can go up to \n\uD835\uDC5A+\uD835\uDC5B\nm+n, representing the maximum length of a path in the grid. So, the space complexity for the call stack is \n\uD835\uDC42(\uD835\uDC5A+\uD835\uDC5B)\nO(m+n).\nVisited Array:\n\nThe vis array is a 2D boolean array of size \n\uD835\uDC5A\xD7\uD835\uDC5B\nm\xD7n, which takes \n\uD835\uDC42(\uD835\uDC5A\xD7\uD835\uDC5B)\nO(m\xD7n) space.\nMemoization Table:\nThe memoization table (hm) stores results for at most \n\uD835\uDC5A\xD7\uD835\uDC5B\xD7\uD835\uDC3B\nm\xD7n\xD7H unique states, which takes \n\uD835\uDC42(\uD835\uDC5A\xD7\uD835\uDC5B\xD7\uD835\uDC3B)\nO(m\xD7n\xD7H) space.\nThus, the overall space complexity is \n\uD835\uDC42(\uD835\uDC5A\xD7\uD835\uDC5B\xD7\uD835\uDC3B)\nO(m\xD7n\xD7H) due to the memoization table.******\n\n# Code\n```java []\nclass Solution {\n    public boolean solve(List<List<Integer>> al,boolean vis[][],int i,int j,int m,int n,int h,HashMap<String,Boolean> hm)\n    {\n       \n        if(i<0||j<0||i>=m||j>=n||vis[i][j])\n        {\n            return false;\n        }\n        if(al.get(i).get(j)==1)\n        {\n            h--;\n        }\n         if(h<=0)\n        {\n            return false;\n        }\n        if(i==m-1&&j==n-1)\n        {\n            // System.out.println(h);\n            return true;\n        }\n        String str=i+"*"+j+"*"+h;\n        if(hm.containsKey(str))\n        {\n            return hm.get(str);\n        }\n       \n         \n        boolean a=false,b=false,c=false,d=false;\n        \n        vis[i][j]=true;\n        a=solve(al,vis,i+1,j,m,n,h,hm);\n        if(!a)\n        {\n            b=solve(al,vis,i,j+1,m,n,h,hm);\n            if(!b)\n            {\n                c=solve(al,vis,i-1,j,m,n,h,hm);\n                if(!c)\n                {\n                    d=solve(al,vis,i,j-1,m,n,h,hm);\n                }\n            }\n        }\n        vis[i][j]=false;\n        hm.put(str,a|b|c|d);\n        return a|b|c|d;\n\n    }\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        boolean vis[][]=new boolean[grid.size()][grid.get(0).size()];\n        for(int i=0;i<vis.length;i++)\n        {\n            for(int j=0;j<vis[0].length;j++)\n            {\n                vis[i][j]=false;\n            }\n        }\n        HashMap<String,Boolean> hm=new HashMap<>();\n       return solve(grid,vis,0,0,vis.length,vis[0].length,health,hm);\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Ordered Map', 'Java']