174. 地下城游戏

https://leetcode-cn.com/problems/dungeon-game/

解法一：dp

求初始最低血量，即按最佳路径到达终点时血量为1。逆向思维，从终点走回起点，自底向上dp。由于反向，每次减去dungeon[i][j]上的血量，因此用hp[i][j]表示(i,j)处所需要的最低血量，易知(i,j)来自右边和下边的较小值，注意最低血量不能<=0，即一旦出现hp<0，则将其置为1。

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        n = len(dungeon)
        m = len(dungeon[0])
        hp = [[0] * m for _ in range(n)]  #dp
        #初始化，处理边界
        #终点
        need = 1 - dungeon[n-1][m-1]
        hp[n-1][m-1] = need if need > 0 else 1
        #右边界
        for i in range(n-2, -1, -1):
            need = hp[i+1][m-1] - dungeon[i][m-1]
            hp[i][m-1] = need if need > 0 else 1
        #下边界
        for j in range(m-2, -1, -1):
            need = hp[n-1][j+1] - dungeon[n-1][j]
            hp[n-1][j] = need if need > 0 else 1
        #其他区域
        for i in range(n-2, -1, -1):
            for j in range(m-2, -1, -1):
                need = min(hp[i+1][j], hp[i][j+1]) - dungeon[i][j]
                hp[i][j] = need if need > 0 else 1
        return hp[0][0]

右侧和下侧增加辅助边hp=无穷大，可以简化处理边界的代码

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        n = len(dungeon)
        m = len(dungeon[0])
        hp = [[sys.maxsize] * (m+1) for _ in range(n+1)]  #dp
        #辅助求终点hp
        hp[n][m-1] = hp[n-1][m] = 1
        for i in range(n-1, -1, -1):
            for j in range(m-1, -1, -1):
                need = min(hp[i+1][j], hp[i][j+1]) - dungeon[i][j]
                hp[i][j] = need if need > 0 else 1
        return hp[0][0]