LeetCode题：174. 地下城游戏

一、题目要求

174. 地下城游戏

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

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

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

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

返回确保骑士能够拯救到公主所需的最低初始健康点数。

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

示例 1：

输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]

输出：7

解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。

示例 2：

输入：dungeon = [[0]]

输出：1

二、解题思路

这题我们用到动态规划的思想，分析题目，我们要从左上角走到右下角，求我们最小初始健康点数是多少。

（1）状态表示

按往常经验，我们喜欢以某个点为终点，填这个位置在dp表中的值是多少，因为在这里，如果以某个点为终点，从前面到这个位置所需要的最小健康点数，就是前面消耗健康点数到这个位置还剩1个健康点数，但到这个位置还剩一个健康点数，要是没到右下角呢，还要走好多步，肯定是还没到右下角就已经死掉了。

所以，这里的状态表示：定义以某个位置为起点，到达右下角所需要的最小健康点数。

（2）状态转移方程

如图：

我们想在dp表的四角星位置放值，放的是在原表中从四角星位置到右下角所需最小健康点数，那么，我们知道每个dp表放的都是当前位置到右下角所需健康的最小点数，设当前点数为x，要能从当前位置走到右下角，那么走到下一个位置时的位置，还有的点数要大于等于下一个位置的点数，设原表为d，有一个新建出的dp表，

所以我们推导出：x + d[ i ][ j ] >= dp[ i + 1 ][ j ] 或 x + d[ i ][ j ] >= dp[ i ][ j + 1 ]

所以，x = dp[ i + 1 ][ j ] - d[ i ][ j ] 或 x = dp[ i ][ j + 1 ] - d[ i ][ j ]

那么我们就要就要从右边或者下边，拿一个点数最小的值，走到下一步还需要的健康点数，当然是少的符合题目要求。

合并：x = min（dp[ i + 1 ][ j ]，dp[ i ][ j + 1 ]） - d[ i ][ j ]

特殊情况：当前位置如果是一个很大的正整数，也就是一个大血包，那么x就会算出负数，这时候就不符合我们的预期了，因为当前位置的点数是负数，也可以走到右下角，就不符合题目要求了，负数早就死了，所以我们当前x值大于0时，就不做处理，x还是原来的值，当x值小于等于0时，当前位置就放一个1，至少有血还能继续往下走。

推出：当前位置的值：max（1，x）

（3）初始化dp表

根据我们定义的状态表示，我们要知道下面和左边的dp表值，才能推出当前的dp表值，所以最后一行和最后一列可能会数组越界，我们多加最后一行和最后一列，并且两个位置初始化为1，其他位置初始化为正无穷，如图：

因为，骑士要到右下角，最后至少必须要有1个健康点数，才能到右下角，说明到右下角值至少需要1个健康点数，而其他位置初始化为正无穷是为了不影响最后一行和最后一列填表，比如最后一行，处除了右下角，只能往往右边走，最后一列，只能往下走。所以得到的是右边的dp值，右边的值肯定比正无穷小。

（4）填表顺序

从右到左，从下到上

（5）返回值

return dp[0][0]

三、代码

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        //1、创建dp表
        int row = dungeon.length;//行
        int col = dungeon[0].length;//列
        int[][] dp = new int[row + 1][col + 1];
        //2、初始化dp表
        for(int i = 0; i < col + 1; i++) {
            //初始化最后一行
            dp[row][i] = Integer.MAX_VALUE;
        }
        dp[row][col - 1] = 1;//最后一行的特殊位置
        for(int i = 0; i < row + 1; i ++) {
            //初始化最后一列
            dp[i][col] = Integer.MAX_VALUE;
        }
        dp[row - 1][col] = 1;//最后一列的特殊位置
        //3、填dp表(顺序：从右到左，从下到上)
        for(int i = row - 1; i >= 0; i--) {
            for(int j = col - 1; j >= 0; j--) {
                int min = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, min);
            }
        }
        //4、返回值
        return dp[0][0];
    }
}