LeetCode题：174. 地下城游戏

男娘i 2024-02-05 13:22 62阅读 0赞

**目录**

一、题目要求

二、解题思路

（1）状态表示

（2）状态转移方程

（3）初始化dp表

（4）填表顺序

（5）返回值

三、代码

--------------------

## 一、题目要求 ##

> [174. 地下城游戏][174.]
> 
> 恶魔们抓住了公主并将她关在了地下城 `dungeon` 的 **右下角** 。地下城是由 `m x n` 个房间组成的二维网格。我们英勇的骑士最初被安置在 **左上角** 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
> 
> 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
> 
> 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为*负整数*，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 *0*），要么包含增加骑士健康点数的魔法球（若房间里的值为*正整数*，则表示骑士将增加健康点数）。
> 
> 为了尽快解救公主，骑士决定每次只 **向右** 或 **向下** 移动一步。
> 
> 返回确保骑士能够拯救到公主所需的最低初始健康点数。
> 
> **注意：**任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
> 
> **示例 1：**
> 
> ![fa9b4703aee4241cff150e221c9fb121.jpeg][]
> 
>     输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
>     输出：7
>     解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
> 
> **示例 2：**
> 
>     输入：dungeon = [[0]]
>     输出：1

## 二、解题思路 ##

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

### （1）状态表示 ###

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

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

### （2）状态转移方程 ###

如图：

![a7b0eb12aee146fc8e92f40181c7166c.png][]

我们想在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，其他位置初始化为正无穷，如图：

![8f080e6d04034056a377bf781334a647.png][]

因为，骑士要到右下角，最后至少必须要有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];
        }
    }

[174.]: https://leetcode.cn/problems/dungeon-game/
[fa9b4703aee4241cff150e221c9fb121.jpeg]: https://img-blog.csdnimg.cn/img_convert/fa9b4703aee4241cff150e221c9fb121.jpeg
[a7b0eb12aee146fc8e92f40181c7166c.png]: https://img-blog.csdnimg.cn/direct/a7b0eb12aee146fc8e92f40181c7166c.png
[8f080e6d04034056a377bf781334a647.png]: https://img-blog.csdnimg.cn/direct/8f080e6d04034056a377bf781334a647.png