LC 0174 [H] Dungeon Game - ALawliet/algorithms GitHub Wiki

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)