题目

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2 (K) -3 3 -5 -10 1 10 30 -5 (P)

说明:

骑士的健康点数没有上限。

任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

思路

参考了评论中的答案，使用动态规划 核心思路是：每次只能往右边或者下面走，那么如果你知道了往右边走需要的最小生命代价和往下面需要的最小生命代价，那么你就知道了当前需要的最小代价 使用二维数组来保存最小生命代价，life[i][j]表示从i，j开始走到右下角的最小生命代价 从右下开始往上动态规划，初始话最小代价是1，如果当前不需要额外的生命代价的话，那么当前的最小生命代价就是1，如果需要额外的代价的话，那么最小生命代价就是额外需要的代价。 说的比较绕口，代码应该比较好理解，总的思路就是，如果后面不需要额外生命，那么你只需要保证能走到当前就可以了，如果后面需要额外代价，那么你需要保证能走到当前并且+后面的额外生命代价

java代码

class Solution {
    // 求骑士走到右下角的最低生命值
    // 只能右或者下
    // DP
    public int calculateMinimumHP(int[][] dungeon) {
        int row = dungeon.length;
        int col = dungeon[0].length;
        int[][] life = new int[row][col]; // life[i][j] 表示i,j的时候需要的最小生命值，肯定不能小于1
        // 初始化
        if(dungeon[row - 1][col - 1] < 0){
            life[row - 1][col - 1] = -dungeon[row - 1][col - 1] + 1;
        }else {
            life[row - 1][col - 1] = 1;
        }
        // 初始化最后一列
        for(int i = row - 2; i >= 0; i--){
            if(life[i+1][col-1] == 1){ // 表示后面的可以自己满足
                life[i][col-1] = Math.max(1,-dungeon[i][col - 1] + 1);
            }else{ // 后面的不可以满足
                life[i][col-1] = Math.max(life[i+1][col-1] - dungeon[i][col - 1],1);
            }
        }
        // 初始话最后一行
        for(int j = col - 2; j >= 0; j --){
            if(life[row - 1][j+1] == 1){
                life[row-1][j] = Math.max(1,-dungeon[row-1][j]+1);
            }else{
                life[row-1][j] = Math.max(life[row-1][j+1]-dungeon[row-1][j],1);
            }
        }
        for(int i = row - 2; i >= 0; i--){
            for(int j = col - 2; j>= 0; j--){
                int min = Math.min(life[i][j+1],life[i+1][j]);
                if(min == 1){ // 后面可以满足
                    life[i][j] = Math.max(1,-dungeon[i][j]+1);
                }else{
                    life[i][j] = Math.max(1,min-dungeon[i][j]);
                }
            }
        }
        return life[0][0];
    }
}

python代码

class Solution:
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        row, col = len(dungeon), len(dungeon[0])
        mem = [[0]*col for _ in range(row)]

        for i in range(row-1,-1,-1):
            for j in range(col-1,-1,-1):
                if i == row-1 and j == col-1:
                    mem[i][j] = max(0, -dungeon[i][j])
                elif i == row-1:
                    mem[i][j] = max(0, mem[i][j+1] - dungeon[i][j])
                elif j == col-1:
                    mem[i][j] = max(0, mem[i+1][j] - dungeon[i][j])
                else:
                    mem[i][j] = max(0, min(mem[i+1][j], mem[i][j+1]) - dungeon[i][j])
                
        return mem[0][0] + 1