6 lines Python, 8 lines Ruby

  • 13

    Just some DP.


    def calculateMinimumHP(self, dungeon):
        n = len(dungeon[0])
        need = [2**31] * (n-1) + [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[0]

    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[0].size - 1
        need = [1/0.0] * n + [1]
        dungeon.reverse_each do |row|
            n.downto(0) do |j|
                need[j] = [need[j..j+1].min - row[j], 1].max

  • 0

    Can you explain this problem Stefan? Especially why dp is from right-bottom?

  • 0

    The running time varies. Sometimes it only beats 20% sometimes 80%.

  • 1

    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

  • 0
    This post is deleted!

  • 0

    Can someone please explain why 'need' is one dimension instead of two-dimension? What exactly does 'need[i]' mean? I thought 'need[i][j]' means the minimum health needed at grid[i][j] in order to reach the last grid. Thanks!

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.