python DP solution O(n) space


  • 0

    When using dp to solve this problem, we need reverse thinking: start from the last cell then ...(general dp)

     import sys
    class Solution(object):
        def calculateMinimumHP(self, dungeon):
            row_num = len(dungeon)
            col_num = len(dungeon[0])
            needs = [sys.maxint]*col_num
            needs[-1] = 0 if dungeon[-1][-1]>0 else -dungeon[-1][-1]
            for i in range(row_num-1, -1, -1):
                for j in range(col_num-1, -1, -1):
                    if j==col_num-1 and i==row_num-1:
                        continue
                    right = needs[j+1] if j+1<col_num else sys.maxint
                    down = needs[j]
                    needs[j] = 0 if dungeon[i][j]-min(right, down)>=0 else -dungeon[i][j]+min(right, down)
            return needs[0]+1
    

Log in to reply
 

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