LeetCode174. 地下城游戏

题目

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。链接

思路

能想到动态规划，但是得从终点开始dp。。
矩阵为int[][] dungeon，设行数为row，列数为col，dp[row][col]为动态规划矩阵。

• 对于终点位置，所需的最小生命值为 max(1, 1 - dungeon[row - 1][col - 1])。解释：若终点点数≥0，生命值为1最小，若为负数，需要-dungeon[i][j] + 1，即生命值至少得是这个负数的绝对值加一。
• 对于最后一行，dp[i][j] = max(1, dp[i][j + 1] - dungeon[i][j])。
  解释：
  若当前点数为负，则dp[i][j] = dp[i][j + 1] + abs(dungeon[i][j])。
  若当前点数≥0，则dp[i][j] = max(1, dp[i][j + 1] - dungeon[i][j])。如果dp[i][j + 1] - dungeon[i][j] <= 0，说明走到当前格子的生命值只需要为1，再加dungeon[i][j]的生命值补充，就可满足走到dungeon[i][j + 1]；否则走到dungeon[i][j + 1]的最小值为dp[i][j + 1] - dungeon[i][j]，即经过当前格子的生命值补充的最小生命值，正好满足走到dungeon[i][j + 1]。两种情况合并的写即为上述。
• 最后一列和最后一行同理
• 对于中间的位置，取右，下两个方向所需生命值小的，再减去当前点数，和1进行比较，道理同上。

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int row = dungeon.length;
        int col = dungeon[0].length;
        int[][] dp = new int[row][col];
        
        for(int i = row - 1; i >= 0; i--){
            for(int j = col - 1; j >= 0; j--){
                if(i == row - 1 && j == col - 1){
                    //当终点≥0，生命值为1即可，若为负数，需要-dungeon[i][j]+1
                    dp[i][j] = Math.max(1, 1 - dungeon[i][j]);
                } else if(i == row - 1){
                    dp[i][j] = Math.max(1, dp[i][j + 1] - dungeon[i][j]);
                } else if(j == col - 1){
                    dp[i][j] = Math.max(1, dp[i + 1][j] - dungeon[i][j]);
                } else {
                    dp[i][j] = Math.max(1, 
                    //取右，下两个方向所需生命值较小的
                    Math.min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j]);
                }
            }
        }
        return dp[0][0];
    }
}