Solution For Minimum Health To Beat Game

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]

Step by Step Implementation For Minimum Health To Beat Game

class Solution {
    public int minHealth(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        
        // minimum health required at the end
        int[][] dp = new int[m][n];
        
        dp[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);
        
        for(int i = m - 2; i >= 0; i--){
            dp[i][n - 1] = Math.max(dp[i + 1][n - 1] - dungeon[i][n - 1], 1);
        }
        
        for(int j = n - 2; j >= 0; j--){
            dp[m - 1][j] = Math.max(dp[m - 1][j + 1] - dungeon[m - 1][j], 1);
        }
        
        for(int i = m - 2; i >= 0; i--){
            for(int j = n - 2; j >= 0; j--){
                int down = Math.max(dp[i + 1][j] - dungeon[i][j], 1);
                int right = Math.max(dp[i][j + 1] - dungeon[i][j], 1);
                dp[i][j] = Math.min(down, right);
            }
        }
        
        return dp[0][0];
    }
}

class Solution:
    def minHealth(self, dungeon):
        # Base case
        if not dungeon:
            return 
        # Get the dimensions of the dungeon
        m = len(dungeon)
        n = len(dungeon[0])
        # Create a 2D array to store minimum health required at each cell
        dp = [[0 for i in range(n)] for j in range(m)]
        # Fill in the base case 
        dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
        # Fill in the first 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 in the first 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 rest of the array    
        for i in range(m-2, -1, -1):
            for j in range(n-2, -1, -1):
                dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
        # Return the minimum health required
        return dp[0][0]

/**
 * @param {number[][]} dungeon
 * @return {number}
 */
 
 //dp from bottom right
var calculateMinimumHP = function(dungeon) {
    let dp = new Array(dungeon.length + 1).fill(null).map(() => new Array(dungeon[0].length + 1).fill(Number.MAX_SAFE_INTEGER));
    dp[dungeon.length][dungeon[0].length - 1] = 1;
    dp[dungeon.length - 1][dungeon[0].length] = 1;
    
    for (let i = dungeon.length - 1; i >= 0; i--) {
        for (let j = dungeon[0].length - 1; j >= 0; j--) {
            let need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
            dp[i][j] = need <= 0 ? 1 : need;
        }
    }
    return dp[0][0];
};

class Solution {
public:
    int minHealth(vector>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector> dp(m, vector(n, 0));
        dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);
        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        for (int j = n - 2; j >= 0; j--) {
            dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};

using System; 

public class Solution { 
    public int FindMinHealth(int[][] dungeon) { 
        // check for edge cases 
        if (dungeon == null || dungeon.Length == 0) { 
            return 0; 
        } 
         
        int rows = dungeon.Length; 
        int cols = dungeon[0].Length; 
         
        // dp array 
        int[][] dp = new int[rows][]; 
        for (int i = 0; i < rows; i++) { 
            dp[i] = new int[cols]; 
        } 
         
        // fill in the dp array 
        dp[rows - 1][cols - 1] = Math.Max(1, 1 - dungeon[rows - 1][cols - 1]); 
         
        for (int i = rows - 2; i >= 0; i--) { 
            dp[i][cols - 1] = Math.Max(1, dp[i + 1][cols - 1] - dungeon[i][cols - 1]); 
        } 
         
        for (int j = cols - 2; j >= 0; j--) { 
            dp[rows - 1][j] = Math.Max(1, dp[rows - 1][j + 1] - dungeon[rows - 1][j]); 
        } 
         
        for (int i = rows - 2; i >= 0; i--) { 
            for (int j = cols - 2; j >= 0; j--) { 
                dp[i][j] = Math.Max(1, Math.Min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]); 
            } 
        } 
         
        // return the value in the top left corner of the dp array 
        return dp[0][0]; 
    } 
}