# Python DP solution 60ms

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

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