Question: https://leetcode.com/problems/dungeon-game/
Question Name: Dungeon Game
The challenge is a DP question. Let minHPFromHere be a 2D matrix with the size of input dungeon game. minHPFromHere[i][j] is the minimum HP to rescue the princess, if the input[i][j] is the initial position.
If the knight standed at position input[i][j], he has two choices: go right or go down. If he went right, we can see: minHPFromHere[i][j] + input[i][j] >= minHPFromHere[i][j+1]. As long as we want to compute the minimum HP, we get: minHPFromHere[i][j] + input[i][j] = minHPFromHere[i][j+1]. Therefore, minHPFromHere[i][j] = minHPFromHere[i][j+1] – input[i][j]. At the same time, the minimum HP is always 1+. In sum, we can get minHPFromHere[i][j] = max(1, minHPFromHere[i][j+1] – input[i][j]). Similarly, if he went down, minHPFromHere[i][j] = max(1, minHPFromHere[i+1][j] – input[i][j]). Combining these two cases together, we get the DP as:
minHPFromHere[i][j] = min( max(1, minHPFromHere[i][j+1] – input[i][j]), max(1, minHPFromHere[i+1][j] – input[i][j]) )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution: # @param dungeon, a list of lists of integers. # @return a integer. def calculateMinimumHP(self, dungeon): if len(dungeon) == 0 or len(dungeon[0]) == 0: return 1 minHPFromHere = [0xFFFF] * len(dungeon[0]) # Practically positive infinity. minHPFromHere[-1] = 1 # The minimum HP to be live. for xPos in xrange(len(dungeon)-1, -1, -1): # From bottom to top. # Handle the rightmost cell. minHPFromHere[-1] = max(1, minHPFromHere[-1] - dungeon[xPos][-1]) # Handle the other cells from right to left. for yPos in xrange(len(dungeon[0])-2, -1, -1): toRight = max(1, minHPFromHere[yPos + 1] - dungeon[xPos][yPos]) toDown = max(1, minHPFromHere[yPos] - dungeon[xPos][yPos]) minHPFromHere[yPos] = min(toRight, toDown) return minHPFromHere[0] |