Python, dungeon game

  • 0

    Just a solution sharing, using one-way DP.

     class Solution(object):
        def calculateMinimumHP(self, dungeon):
            :type dungeon: List[List[int]]
            :rtype: int
            row=len(dungeon); col=len(dungeon[0])
            board=[0 for i in xrange(col)]
            board[-1]=max(1, 1-dungeon[-1][-1])
            for j in xrange(col-2, -1, -1):
                board[j]=max(1, board[j+1]-dungeon[row-1][j])
            for i in xrange(row-2, -1, -1):
                board[-1]=max(1, board[-1]-dungeon[i][-1])
                for j in xrange(col-2, -1, -1):
                    board[j]= max(1, min(board[j]-dungeon[i][j], board[j+1]-dungeon[i][j]))
            return board[0]

Log in to reply

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