Dungeon Game | LeetCode | Solution Explained
Dungeon Game is a Hard level problem on LeetCode, requiring us to break the problem down into two big parts. First, we want to know how to evaluate a path, and second, we want to know how to enumerate all the paths. We can use some basic observations for the first and depth first search (DFS) for the second. Problem link.
Contents hide
LOGIC
- Evaluate a path:
[2, -13, 3, -5]
- find the initial health
- the final health has to be 1
- let’s start from the end?
- required health from the end to the start
- 1–5 = 6
- 6-3 = 3
- 3–13 = 16
- 16-2 = 14
- ans = 14
- Find the best path
- Enumerate all the paths
- Evaluate all the paths
dfs(x, y): return required_health
- start from:
dfs(0, 0)
- base:
(x, y) == (m-1, n-1)
- spawns off:
dfs(x+1, y)
anddfs(x, y+1)
- start from:
Recursive DFS Code
class Solution: def calculateMinimumHP(self, grid: List[List[int]]) -> int: @lru_cache(None) def dfs(x, y): if x >= m or y >= n: return inf if (x, y) == (m-1, n-1): req = -grid[x][y] return 1 if req <= 0 else req+1 req = min(dfs(x+1, y), dfs(x, y+1)) req -= grid[x][y] return 1 if req <= 0 else req m, n = len(grid), len(grid[0]) return dfs(0, 0)
Iterative DP Code

Iterative dp is mostly a translation of the recursive code. There’s the edge case that needs to be handled.
- Recall how we had “walls” for the dfs, saying that we need
inf
health required - In this case, we have to do the same
- Except for one place where
dp[m][n-1] = dp[m-1][n] = 1
- This is because of the case of
(x, y) = (m-1, n-1)
, where we try to accessdp[x+1][y]
anddp[x][y+1]
and take their minimum - Thus, the line
dp[m][n-1] = dp[m-1][n] = 1
becomes the base case
class Solution: def calculateMinimumHP(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) dp = [[inf]*(n+1) for _ in range(m+1)] dp[m][n-1] = dp[m-1][n] = 1 for x in reversed(range(m)): for y in reversed(range(n)): dp[x][y] = min(dp[x+1][y], dp[x][y+1]) dp[x][y] -= grid[x][y] dp[x][y] = 1 if dp[x][y] <= 0 else dp[x][y] return dp[0][0]
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022