Dungeon Game

Problem: Dungeon Game

We can do dynamic programming from down-right corner to up-left corner. Note that if we have -5 at current position and 30 at next step, we need have at least 6 health to pass these 2 steps. Besides, even to go to only a position with 30, we need to have at least 1 health.

Code in Python:

class Solution(object):
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        m, n = len(dungeon), len(dungeon[0])
        for i in xrange(m-1, -1, -1):
            for j in xrange(n-1, -1, -1):
                if i == m-1 and j != n-1: dungeon[i][j] = min(dungeon[i][j] + min(dungeon[i][j+1], 0), 0)
                elif j == n-1 and i != m-1: dungeon[i][j] = min(dungeon[i][j] + min(dungeon[i+1][j], 0), 0)
                elif i != m-1 and j != n-1: dungeon[i][j] = min(dungeon[i][j] + max(dungeon[i][j+1], dungeon[i+1][j]), 0)
        return 1 - min(dungeon[0][0], 0)