My o(mn) space and time solution for this problem


  • 0
    R

    class Solution:
    # @param dungeon, a list of lists of integers
    # @return a integer
    def calculateMinimumHP(self, dungeon):
    if dungeon==None:
    return None
    m=len(dungeon)
    n=len(dungeon[0])
    DP=[[i for i in range(n)]for j in range(m)]
    DP[m-1][n-1]=1-dungeon[m-1][n-1]
    for i in range(m-1,-1,-1):
    for j in range(n-1,-1,-1):
    if i+1>=m and j+1<n:
    DP[i][j]=DP[i][j+1]-dungeon[i][j]
    elif i+1<m and j+1>=n:
    DP[i][j]=DP[i+1][j]-dungeon[i][j]
    elif i+1<m and j+1<n:
    DP[i][j]=min(DP[i][j+1]-dungeon[i][j],DP[i+1][j]-dungeon[i][j])
    if DP[i][j]<=0:
    DP[i][j]=1
    return DP[0][0]


Log in to reply
 

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