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.

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 <= 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]

Tanishq Chaudhary

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