Solution to Dungeon Game by LeetCode

27 Apr

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]) )