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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Dungeon Game

Difficulty: Hard

Problem Description

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons (represented by negative integers), while other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers). To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Return the knight's minimum initial health so that he can rescue the princess.

Key Insights

  • The knight must navigate a 2D grid while managing his health points.
  • Health points can decrease due to negative values (demons) or increase due to positive values (magic orbs).
  • The knight can only move right or down, creating a specific pathing requirement.
  • The goal is to determine the minimum initial health required to ensure the knight reaches the princess without dying.

Space and Time Complexity

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

Solution

The solution can be approached using dynamic programming. We will create a 2D array dp where dp[i][j] will store the minimum health required to reach the princess from cell (i, j). We will fill this array starting from the bottom-right corner (where the princess is) and move to the top-left corner (the knight's starting point). The value in the dp array will be calculated based on the health points in the current cell and the health needed in the cells below and to the right. After filling the dp array, the value at dp[0][0] will provide the minimum initial health required for the knight.

Code Solutions

def calculateMinimumHP(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    dp = [[0] * n for _ in range(m)]
    
    # Starting from the princess's room
    dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
    
    # Fill the last row
    for j in range(n-2, -1, -1):
        dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
    
    # Fill the last column
    for i in range(m-2, -1, -1):
        dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
    
    # Fill the rest of the dp table
    for i in range(m-2, -1, -1):
        for j in range(n-2, -1, -1):
            min_health_on_exit = min(dp[i+1][j], dp[i][j+1])
            dp[i][j] = max(1, min_health_on_exit - dungeon[i][j])
    
    return dp[0][0]
← Back to All Questions