DP based solution for beginners | Standard Template
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition directly comes from the point that we will perform BFS in all directions 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition directly comes from the point that we will perform BFS in all directions from each cell until we reach the target. If in any path during the traversal, our health becomes less than 0 then that path is invalid or else continue the BFS.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTraverse from $$(0,0)$$ in all possible direction using a $$helper$$ function. Mark the cell as visited and then backtrack from there.\nThis will cover all the paths. If in any path, the indexes becomes invalid or the $$health$$ becomes less than $$0$$ then that path is invalid.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n*m)$$ , where $$n$$ represents the number of rows and $$m$$ represents the number of columns.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n*m*h) + O(n*m)$$ , Where $$n$$ represents number of rows and $$m$$ represents number of columns and $$h$$ represents health.\n# Code\n```java []\nclass Solution {\n    int rows;\n    int cols;\n    boolean[][] visited;\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        //Can move in all directions,\n        //Start from (0,0) and end at (m,n);\n        // For each grid[i][j]=1, health decreases by 1.\n        rows = grid.size();\n        cols = grid.get(0).size();\n        visited = new boolean[rows][cols];\n        int[][][] dp = new int[rows][cols][health+1];\n        for(int[][] d:dp) {\n            for(int[] a:d)Arrays.fill(a,-1);\n        }\n        return helper(0,0,grid,health,dp);\n    }\n\n    private boolean helper(int x,int y,List<List<Integer>> grid, int health,int[][][] dp) {\n        if(!isValid(x,y) || visited[x][y] || health <=0)return false;\n        if(x == rows-1 && y == cols-1)return health>grid.get(x).get(y);\n        if(dp[x][y][health] != -1)return dp[x][y][health] ==1;\n        //Mark the current cell as visited \n        visited[x][y] = true;\n        health -=grid.get(x).get(y);\n        boolean up = helper(x-1,y,grid,health,dp);\n        boolean down = helper(x+1,y,grid,health,dp);\n        boolean left = helper(x,y-1,grid,health,dp);\n        boolean right = helper(x,y+1,grid,health,dp);\n        health += grid.get(x).get(y);\n        visited[x][y]=false; // Backtrack from here \n        dp[x][y][health] = up || down || left || right ? 1:0;\n        return up || down || left ||right;\n    }\n\n    private boolean isValid(int x,int y) {\n        return x>=0 && y>=0 && x<rows && y<cols;\n    }\n}\n```
['Dynamic Programming', 'Backtracking', 'Breadth-First Search', 'Java']