# My 15 liner python DP solution with comments

• We start from bottom right corner and solve towards top left corner. At each cell we compute
the energy(x[i][j]) it needs from prev cells(top/left) to let the king pass alive. It does so by
checking it's own energy requirement and the min energy required by next cells (down/right).
In case if cell has enough magic orbs, it just requires king to arrive alive, i.e. value 1

``````class Solution(object):
def calculateMinimumHP(self, M):
"""
:type dungeon: List[List[int]]
:rtype: int
"""
r = len(M)
c = len(M[0])
x = [[0 for x in range(c)] for y in range(r)]
# set energy requirement of bottom right cell
x[r-1][c-1] = 1-M[r-1][c-1] if M[r-1][c-1] < 0 else 1

for row in range(r-1,-1,-1):
for col in range(c-1,-1,-1):
if not(row == r-1 and col == c-1): #exclude bottom right cell
to_down  = x[row+1][col] if row < r-1 else sys.maxint # boundary conditions
to_right = x[row][col+1] if col < c-1 else sys.maxint
x[row][col] = max(1, min(to_down, to_right) - M[row][col])

return x[0][0]``````

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