LeetCode题:174. 地下城游戏

简介: 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];
    }
}
相关文章
|
3月前
|
Go
golang力扣leetcode 1823.找出游戏的获胜者
golang力扣leetcode 1823.找出游戏的获胜者
24 0
|
3月前
leetcode-1996:游戏中弱角色的数量
leetcode-1996:游戏中弱角色的数量
22 0
|
3月前
leetcode:292. Nim 游戏(数学推理)
leetcode:292. Nim 游戏(数学推理)
18 0
|
3月前
|
算法 Java 测试技术
[Java·算法·中等] LeetCode 45. 跳跃游戏 II 详细解读
[Java·算法·中等] LeetCode 45. 跳跃游戏 II 详细解读
27 0
|
3月前
leetcode-529:扫雷游戏
leetcode-529:扫雷游戏
20 0
|
3月前
|
存储
leetcode-289:生命游戏
leetcode-289:生命游戏
24 0
|
3月前
leetcode-174:地下城游戏
leetcode-174:地下城游戏
24 0
|
3月前
|
SQL
leetcode-SQL-550. 游戏玩法分析 IV
leetcode-SQL-550. 游戏玩法分析 IV
22 1
|
3月前
|
SQL
leetcode-SQL-511. 游戏玩法分析 I
leetcode-SQL-511. 游戏玩法分析 I
19 0
|
17天前
|
机器学习/深度学习 算法
力扣刷题日常(一)
力扣刷题日常(一)
18 2