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]
    

  • 0

    To all those wondering why we have added an extra row and an extra column, refer Minimum Path Sum. Remember the two extra for loops (outside the main ones)? It is to avoid that.

    Please let me know if you have a different opinion.

    Thanks,
    BatCoder.


  • 0
    A

    How does this account for the positive health a knight has accumulated in getting to a given position?
    For example: If a knight is getting into a position with health 5000, it doesn't matter that dungeon[x,y] is -2000.


Log in to reply
 

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