Concise Python 7 lines, no extra memory


  • 0
    X

    Idea is just same to others, DP from bottom-right corner.

    I use a decreasing steps to calculate from bottom-right to upper-left, and for each steps, get correct x, y coordinates using another loop.

    b is the minimum blood I need to enter to the next step, which is just min(f[x+1][y], f[x][y+1]).

        def calculateMinimumHP(self, dungeon):
            m, n = len(dungeon), len(dungeon[0])
            for steps in range(m + n - 2, -1, -1):
                for x in range(max(0, steps - n + 1), min(steps + 1, m)):
                    y = steps - x
                    b = min(dungeon[x + 1][y] if x + 1 < m else sys.maxint, dungeon[x][y + 1] if y + 1 < n else sys.maxint)
                    dungeon[x][y] = max(1, (b if b != sys.maxint else 1) - dungeon[x][y])
            return dungeon[0][0]

Log in to reply
 

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