174.md

class Solution(object):
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        n = len(dungeon[0])
        m = len(dungeon)
        ans = [[0 for i in range(n)] for j in range(m)]
        ans[m-1][n-1] = max(- dungeon[-1][-1] + 1, 1)
        
        for j in range(n-2, -1, -1):
            ans[-1][j] = max(ans[-1][j+1] - dungeon[-1][j], 1)
        for i in range(m-2, -1, -1):
            ans[i][-1] = max(ans[i+1][-1] - dungeon[i][-1], 1)
        
        for j in range(n-2, -1, -1):
            for i in range(m-2, -1, -1):
                ans[i][j] = max(min(ans[i+1][j], ans[i][j+1])-dungeon[i][j], 1)
        return ans[0][0]

动态规划