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[row1][col1] = 1
for i in range(row2, 1, 1):
dp[i][col1] = max(1, dp[i+1][col1]dungeon[i+1][col1])
for i in range(col2, 1, 1):
dp[row1][i] = max(1, dp[row1][i+1]dungeon[row1][i+1])
for i in range(row2, 1, 1):
for j in range(col2, 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])
Accepted Python DP solution


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(m1, 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]