Dungeon Game
The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of MxN rooms laid out in a 2D grid. Our valiant knight was initially positioned at the top-left corner of the dungeon. The knight needs to reach the princess. The knight has a certain amount of health. If at any point his health drops to 0 or below, he will die and we lose. Some of the rooms in the dungeon contain magic, which either increases or decreases the knight's health. At each cell, the knight can only move either right or down. Find the minimum amount of health the knight needs to have initially so that he will not die in the dungeon.
Constraints:
- 1 <= dungeon.length <= 8
- 1 <= dungeon[0].length <= 8
- -100 <= dungeon[i][j] <= 100
Examples:
Input: [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The knight needs at least 7 health to reach the princess.
Solutions
Dynamic Programming
The solution uses dynamic programming to calculate the minimum health required at each cell. It starts from the bottom-right corner and moves up and left, calculating the minimum health required at each cell based on the minimum health required at the cells below and to the right.
def calculateMinimumHP(dungeon):
rows, cols = len(dungeon), len(dungeon[0]); dp = [[0]*cols for _ in range(rows)]; dp[rows-1][cols-1] = max(1, 1 - dungeon[rows-1][cols-1]); for i in range(rows-2, -1, -1):
dp[i][cols-1] = max(1, dp[i+1][cols-1] - dungeon[i][cols-1]); for j in range(cols-2, -1, -1):
dp[rows-1][j] = max(1, dp[rows-1][j+1] - dungeon[rows-1][j]); for i in range(rows-2, -1, -1):
for j in range(cols-2, -1, -1):
dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]); return dp[0][0]Follow-up:
What if the knight can move in all four directions (up, down, left, right)?
