My 15 liner python DP solution with comments


  • 0
    V

    We start from bottom right corner and solve towards top left corner. At each cell we compute
    the energy(x[i][j]) it needs from prev cells(top/left) to let the king pass alive. It does so by
    checking it's own energy requirement and the min energy required by next cells (down/right).
    In case if cell has enough magic orbs, it just requires king to arrive alive, i.e. value 1

    class Solution(object):
        def calculateMinimumHP(self, M):
            """
            :type dungeon: List[List[int]]
            :rtype: int
            """
            r = len(M)
            c = len(M[0])
            x = [[0 for x in range(c)] for y in range(r)]
            # set energy requirement of bottom right cell
            x[r-1][c-1] = 1-M[r-1][c-1] if M[r-1][c-1] < 0 else 1
            
            for row in range(r-1,-1,-1):
                for col in range(c-1,-1,-1):
                    if not(row == r-1 and col == c-1): #exclude bottom right cell
                        to_down  = x[row+1][col] if row < r-1 else sys.maxint # boundary conditions
                        to_right = x[row][col+1] if col < c-1 else sys.maxint
                        x[row][col] = max(1, min(to_down, to_right) - M[row][col])
            
            return x[0][0]

Log in to reply
 

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