# 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

## 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)` and `dfs(x, y+1)`

## 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 &lt;= 0 else req+1

req = min(dfs(x+1, y), dfs(x, y+1))
req -= grid[x][y]

return 1 if req &lt;= 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 access `dp[x+1][y]` and `dp[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]]) -&gt; 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] &lt;= 0 else dp[x][y]

return dp[0][0]```
##### Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Disjoint Intervals | InterviewBit | Solution Explained

June 12, 2022

##### Capture Regions on Board | InterviewBit | Solution Explained

May 13, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.