C++ DP solution


  • 0
    S

    Here is explanation and code in python, inspired by this -

    class Solution(object):
        def calculateMinimumHP(self, dungeon):
            """
            :type dungeon: List[List[int]]
            :rtype: int
            """
            if not dungeon or len(dungeon) == 0:
                return 0
            
            m = len(dungeon)
            n = len(dungeon[0])
            
            energy = [ [ 0 for j in range(n) ] for i in range(m) ]
            # energy(i,j) = minimum amount of energy needed to survive dungeon[i][j] AND reach dungeon[m-1][n-1]
            #
            # from (i,j) knight can move to either (i+1,j) or (i,j+1)
            # at (i,j) knight will spend dungeon[i][j] energy, 
            # at (i,j) knight will need min(energy(i+1,j), energy(i,j+1)) to one of the next position
            # 
            # energy needed to survive dungeon(i,j) and move to next position is
            #       min(energy(i+1,j), energy(i+1,j)) - dungeon[i][j]
            #
            # this works in cases where dungeon[i][j] is always negative (-dungeon[i][j]) actually becomes (+abs(dungeon[i][j]))
            # but there're certain booster dungeons, in which case energy(i,j) can become negative or zero, 
            # but minimum energy needed to survive and move on to next is 1
            #
            # so energy(i,j) = max(min( energy(i+1,j), energy(i,j+1) ) - dungeon[i][j] , 1)
            
            
            energy[m-1][n-1] = abs(dungeon[m-1][n-1]) + 1 if dungeon[m-1][n-1] < 0 else 1
            for j in range(n-2,-1,-1):
                #energy[m-1][j] = max(energy[m-1][j+1] - dungeon[m-1][j], 1)
                need = energy[m-1][j+1] - dungeon[m-1][j]
                if need <= 0:
                    energy[m-1][j] = 1
                else:
                    energy[m-1][j] = need
            for i in range(m-2,-1,-1):
                #energy[i][n-1] = max(energy[i+1][n-1] - dungeon[i][n-1],1)
                need = energy[i+1][n-1] - dungeon[i][n-1]
                if need <= 0:
                    energy[i][n-1] = 1
                else:
                    energy[i][n-1] = need
            for i in range(m-2,-1,-1):
                for j in range(n-2,-1,-1):
                    #energy[i][j] = max(  min(energy[i+1][j], energy[i][j+1]) - dungeon[i][j] ,1)
                    need = min(energy[i+1][j], energy[i][j+1]) - dungeon[i][j]
                    if need <= 0:
                        energy[i][j] = 1
                    else:
                        energy[i][j] = need
            
            return energy[0][0]
    

Log in to reply
 

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