# 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)`

and`dfs(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 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]]) -> 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