Minimum Health To Beat Game - Leetcode Solution

Problem statement:

Given a list of integers representing the health points of the player at different levels of the game, find the minimum initial health that the player must have in order to beat the game. At each level, the player can either gain or lose some health points. If the player's health drops to zero or less at any point in the game, the game is over. The player wins by reaching the end of the game with at least 1 health point.

Solution approach:

We can solve this problem using dynamic programming. The idea is to start at the end of the game and work backwards towards the beginning. At each level, we will calculate the minimum initial health required to reach the end with at least 1 health point. Let's define dp[i][j] as the minimum initial health required to reach the end of the game starting from level (i, j) with at least 1 health point.

Now, let's look at how we can calculate dp[i][j] for any level (i, j):

1. If (i, j) is the bottom-right corner of the grid (i.e., the end of the game), then dp[i][j] = max(1, 1 - grid[i][j]). This means that the player must have at least 1 health point at the end of the game, so we take the maximum of 1 and the negative of the health points at the last level.

2. If (i, j) is in the last row or last column of the grid (but not the last cell), then dp[i][j] = max(1, dp[i][j+1] - grid[i][j]) or dp[i][j] = max(1, dp[i+1][j] - grid[i][j]), depending on whether we are in the last row or last column, respectively. This means that we first calculate the minimum initial health required to reach the end from the cell to the right or below, and then subtract the health points at the current level.

3. If (i, j) is not in the last row or last column of the grid, then dp[i][j] = max(1, min(dp[i][j+1], dp[i+1][j]) - grid[i][j]). This means that we first calculate the minimum initial health required to reach the end from the cell to the right or below, take the minimum of these two values, and then subtract the health points at the current level.

Now that we have calculated dp[i][j] for all levels (i, j) starting from the end of the game, the answer to the problem is dp[0][0].

Time Complexity:

Since we are traversing through the matrix once, the time complexity of the solution will be O(m*n), where m and n are the number of rows and columns of the matrix, respectively.

Space Complexity:

We are using a 2D array to store the minimum initial health required to reach the end of the game from each level. Therefore, the space complexity of the solution will be O(m*n), where m and n are the number of rows and columns of the matrix, respectively.

Python code:

class Solution: def calculateMinimumHP(self, dungeon: List[List[int]]) -> int: m, n = len(dungeon), len(dungeon[0]) dp = [[0] * n for _ in range(m)]

    dp[-1][-1] = max(1, 1 - dungeon[-1][-1])
    
    for i in range(m-2, -1, -1):
        dp[i][-1] = max(1, dp[i+1][-1] - dungeon[i][-1])
        
    for j in range(n-2, -1, -1):
        dp[-1][j] = max(1, dp[-1][j+1] - dungeon[-1][j])
        
    for i in range(m-2, -1, -1):
        for j in range(n-2, -1, -1):
            dp[i][j] = max(1, min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j])
            
    return dp[0][0]

1