Just some DP.
def calculateMinimumHP(self, dungeon): n = len(dungeon) need = [2**31] * (n-1) +  for row in dungeon[::-1]: for j in range(n)[::-1]: need[j] = max(min(need[j:j+2]) - row[j], 1) return need
Got accepted in 52 ms, faster than all other recent Python submissions (best was 56 ms, achieved by 5.7692%).
def calculate_minimum_hp(dungeon) n = dungeon.size - 1 need = [1/0.0] * n +  dungeon.reverse_each do |row| n.downto(0) do |j| need[j] = [need[j..j+1].min - row[j], 1].max end end need end
I mostly get the logic, but had to do a double-take on the syntax haha. Scan from bottom-right to top left. Need contains the computations from the previous row, although you only need the values from cell directly below and to the right of current cell to compute the current need. Python allows slices to be out of range so it doesn't matter if
need[j:j+2] is on last column. Need initialized to largest positive integer sort of as a "dummy" row so the first row processed (last row in dungeon) is calculated correctly
As to why it needs to start from bottom-right as opposed to top-left...my first solution was DFS (timeout), second attempt was from top-left DP, but the problem with that is you don't have enough information at that point whether to go right or bottom. You could choose the direction that minimizes life needed on current path, or maximizes the health outcome, but neither guarantees you'll reach the end with minimum life necessary. Whereas starting from the end (bottom-right) you know the minimum life you need when landing at the last cell and work backwards from there
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.