Python DP solution 60ms


  • 0
    Y
    class Solution(object):
        def calculateMinimumHP(self, dungeon):
            """
            :type dungeon: List[List[int]]
            :rtype: int
            """
            if not dungeon: return 1
            m,n=len(dungeon),len(dungeon[0])
            mhp=[[0 for j in xrange(n)] for i in xrange(m)]
            
            k=min(m-1,n-1)
            loop=0
            while(loop<k):
                ist=m-1-loop
                jst=n-1-loop
                while(jst>=0):
                    mhp[ist][jst]=self.getNeighborMin(dungeon,m,n,ist,jst,mhp)
                    jst=jst-1
                jst=n-1-loop
                ist=ist-1
                while(ist>=0):
                    mhp[ist][jst]=self.getNeighborMin(dungeon,m,n,ist,jst,mhp)
                    ist=ist-1
                loop=loop+1
            
            if(loop==m-1):
                jst=n-1-loop
                while(jst>=0):
                    mhp[0][jst]=self.getNeighborMin(dungeon,m,n,0,jst,mhp)
                    jst=jst-1
            if(loop==n-1):
                ist=m-1-loop
                while(ist>=0):
                    mhp[ist][0]=self.getNeighborMin(dungeon,m,n,ist,0,mhp)
                    ist=ist-1
            return mhp[0][0]
            
        def getNeighborMin(self,dungeon,m,n,i,j,mhp):
            if(i+1==m and j+1==n): 
                return max(1,1-dungeon[m-1][n-1])
            elif(i+1==m):
                return max(1,mhp[i][j+1]-dungeon[i][j])
            elif(j+1==n):
                return max(1,mhp[i+1][j]-dungeon[i][j])
            else:
                return max(1,min(mhp[i][j+1],mhp[i+1][j])-dungeon[i][j])
    

Log in to reply
 

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