本文主要是介绍LeetCode题:174. 地下城游戏,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
一、题目要求
二、解题思路
(1)状态表示
(2)状态转移方程
(3)初始化dp表
(4)填表顺序
(5)返回值
三、代码
一、题目要求
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];}
}
这篇关于LeetCode题:174. 地下城游戏的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!