# Accepted Python DP solution

• ``````class Solution:
# @param dungeon, a list of lists of integers
# @return a integer
def calculateMinimumHP(self, dungeon):
#If at any point his health point drops to 0 or below, he dies immediately.
#have to make sure at any point health is > 0
#dp[i][j] is minimum health needed when arriving at this grid
#dp[i][j] = min(max(1, dp[right]-right_grid_value), max(1, dp[down]-down_grid_value))
row, col = len(dungeon), len(dungeon[0])
dp = [[0 for x in range(col)] for x in range(row)]
dp[row-1][col-1] = 1
for i in range(row-2, -1, -1):
dp[i][col-1] = max(1, dp[i+1][col-1]-dungeon[i+1][col-1])
for i in range(col-2, -1, -1):
dp[row-1][i] = max(1, dp[row-1][i+1]-dungeon[row-1][i+1])
for i in range(row-2, -1, -1):
for j in range(col-2, -1, -1):
right = max(1, dp[i][j+1]-dungeon[i][j+1])
down = max(1, dp[i+1][j]-dungeon[i+1][j])
dp[i][j] = min(right, down)
return max(1, dp[0][0]-dungeon[0][0])``````

• Here is my answer with O(mn) time but only O(m). Since the dp[i][j] only comes from bottom and left, we can use only one row instead the whole m*n matrix.

``````class Solution(object):
def calculateMinimumHP(self, dungeon):
"""
:type dungeon: List[List[int]]
:rtype: int
"""

m = len(dungeon)

# Create boundary
dp = [9999]*(m+1)
dp[-2] = 1

for j in xrange(len(dungeon[-1])-1, -1, -1):
for i in xrange(m-1, -1, -1):
# We need at leat one point for survive
dp[i] = max(min(dp[i+1], dp[i]) - dungeon[i][j], 1)

return dp[0]``````

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