LC 0174 [H] Dungeon Game - ALawliet/algorithms GitHub Wiki
prereq: Minimum Path Sum
just like Minimum Path Sum except:
- we end pad with 1 instead of 0, we survive with at least 1 instead of exhausting the path cost
- grid[r][c]
instead of+ grid[r][c]
, we can either gain or lose HP instead of just adding to path cost- reset min cost 1 if we fall below 0
each DP cell represents the min HP we need to start from that current cell to get to the end and survive (with at least 1 HP) before we activate that current cell
the inf
padding with the at least 1
assumption makes the setup much cleaner:
[[ -2 -3 3]
[ -5 -10 1]
[ 10 30* -5]]
* while we could technically survive that cell with a min of -24 HP
well according to the rules of this problem that means we'd be dead
so we can move it back within legit bounds by assuming a min of at least 1 HP
6 - 30 = -24 => 1
if T[r][c] < 1: T[r][c] = 1
[[ 7. 5. 2. inf]
[ 6. 11. 5. inf]
[ 1. 1. 6. 1.]
[inf inf 1. inf]]
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
grid = dungeon
rows = len(grid)
cols = len(grid[0])
T = [ [float('inf') for c in range(cols + 1)] for r in range(rows + 1) ]
T[-2][-1] = T[-1][-2] = 1 #
for r in range(rows - 1, -1, -1):
for c in range(cols - 1, -1, -1):
T[r][c] = max(min(T[r+1][c], T[r][c+1]) - grid[r][c], 1) #
return T[0][0]
T/S: O(num rows * num cols)