Proof of why 3D DP solution works
Intuition\nThe intution is relatively simpler as far as the initial thought is concerned. The initial thought was simply to check all the paths and find if any 
# Intuition\nThe intution is relatively simpler as far as the initial thought is concerned. The initial thought was simply to check all the paths and find if any of the paths reaches to the m-1, n-1 cell of the grid.\n\n# Approach\nThe approach was a simple dfs where I will try to go through all the acyclic paths. Then I simply try to memoize the dfs calls based on the three parameters x, y, and health. Now the big question is why is the visited array not the part of the memoized parameters. Look at that in the next Section.\n\n# Proof\nNow Look at the following case : \n```\n0 1 0\n1 0 0\n1 1 0\n\nhealth = 2\n```\nWe first explore the path, say P1, (0,0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) now from this cell i.e. (1, 1) with remaining health = 1 we get false cause its not possible to continue the above path to reach (2, 2) within required health limit. So now the the memoization tbl stores False at [1][1][1]. \n\nNow lets look at another path, say P2, (0, 0) -> (1, 0) -> (1, 1) now from this cell i.e. (1, 1) with remaining health = 1 we will return False cause in the tbl we have stored False at [1][1][1] but it should have returned True because we can continue the above path to reach (2, 2) within required health limit by extending it like (1, 1) -> (1, 2) -> (2, 2).\n\nSo it goes on to show that our approach is incorrect, but our approach will return True for a different path, say P3, the path being (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2).\n\nNow what we need to show is that such a path (like P3) always exsists in cases like these. To show that we need to see that P2 goes through P1 and P1 itself would explore the path P2 is goining through. To frame it differently what I mean is if there is some path which exsists from (1, 1) that reaches (2, 2) and the path goes through P1 then P1 would explore it anyway. Although we incorrectly return False for P2 but P1 itself will explore the path which might reach the cell (2, 2).  \n\n# Complexity\n- Time complexity:\nO(m * n * health)\n\n- Space complexity:\nO(m * n * health) extra Space + O (m * n) stack space\n\nI am sorry for my english and please feel free to have a chat in discussion I will try my best to explain you all my idea and would also appreciate if someone could point out anything that I am missing in my proof.\n\n# Code\n```cpp []\nclass Solution {\n    int m, n;\npublic:\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        m = grid.size();\n        n = grid[0].size();\n        vector<vector<int>> visited(m, vector<int>(n, 0));\n        vector<vector<vector<int>>>tbl(m+1,vector<vector<int>>(n+1,vector<int>(health+1,-1)));\n        if(grid[0][0] == 1)\n            health = health-1;\n        return f(0, 0, grid, health, visited,tbl);\n    }\n\nprivate:\n    bool f(int x, int y, vector<vector<int>>& grid, int health,vector<vector<int>>& visited,vector<vector<vector<int>>>& tbl) {\n        if(tbl[x][y][health] != -1)\n            return tbl[x][y][health];\n        \n        if (x == m - 1 && y == n - 1)\n            return tbl[x][y][health] = health > 0;\n        \n        visited[x][y] = 1;\n        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n\n        for (auto dir : directions) {\n            int newX = x + dir[0];\n            int newY = y + dir[1];\n\n            if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {\n                int newHealth = health - grid[newX][newY];\n                if (newHealth > 0) {\n                    if (f(newX, newY, grid, newHealth, visited,tbl)) {\n                        return tbl[x][y][health] = true;\n                    }\n                }\n            }\n        }\n\n        visited[x][y] = 0;\n\n        return tbl[x][y][health] = false;\n    }\n};\n```
['Dynamic Programming', 'C++']