We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Dungeon Game

Number: 174

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Zoho, Flipkart, Microsoft

Problem Description

Given an m x n grid (dungeon) where each cell contains an integer that may decrease (demons) or increase (magic orbs) the knight’s health, determine the minimum initial health required for the knight to rescue the princess located at the bottom-right cell. The knight starts at the top-left cell and can only move right or down. Health must always be at least 1.

Key Insights

  • Use Dynamic Programming with a reverse (bottom-up) approach starting from the princess’s cell.
  • At each cell, compute the minimum health needed to ensure survival until reaching the princess.
  • The required health at any cell is max(minimum necessary health from the right or down cell minus the current cell value, 1).
  • Boundary initialization is key; set extra row and column cells to a high value (or infinity) except the positions adjacent to the princess’s cell set to 1.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

We solve the problem by initializing a DP table where dp[i][j] represents the minimum health needed at cell (i, j) to eventually reach the princess. We initialize the dp table for boundaries to simulate an “exit” from the dungeon cell with a minimum requirement of 1 health. Then we iterate from the bottom-right cell (princess’s cell) backwards to the top-left cell. For each cell, compute the minimum health needed based on the minimum of the health requirements of the right and bottom neighbors, ensuring that the value is at least 1. This approach guarantees that the knight’s health never falls to 0 or below at any point.

Code Solutions

def calculateMinimumHP(dungeon):
    # Determine the dimensions of the dungeon grid.
    m, n = len(dungeon), len(dungeon[0])
    
    # Create a DP table with an extra row and column for boundary conditions.
    dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
    
    # Set the cells adjacent to the princess's cell to 1.
    dp[m][n - 1] = 1
    dp[m - 1][n] = 1
    
    # Fill the DP table starting from the bottom-right corner moving backwards.
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            # Min health required from right and bottom cells.
            min_next = min(dp[i + 1][j], dp[i][j + 1])
            # Calculate health needed at the current cell.
            dp[i][j] = max(min_next - dungeon[i][j], 1)
    
    return dp[0][0]

# Example usage:
dungeon = [[-2, -3, 3],
           [-5, -10, 1],
           [10, 30, -5]]
print(calculateMinimumHP(dungeon))
← Back to All Questions