珠海网站建设运营公司,wordpress媒体文档,城乡建设网站投稿,html5基础知识地下城游戏
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某…地下城游戏
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
**注意**任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1
!https://assets.leetcode.com/uploads/2021/03/13/dungeon-grid-1.jpg
输入dungeon [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出7
解释如果骑士遵循最佳路径右 - 右 - 下 - 下 则骑士的初始健康点数至少为 7 。示例 2
输入dungeon [[0]]
输出1
提示
m dungeon.lengthn dungeon[i].length1 m, n 2001000 dungeon[i][j] 1000
思路 代码
class Solution {public int calculateMinimumHP(int[][] map) {if(map null || map.length 0) {return 1;}int m map.length,nmap[0].length;int[][] dp new int[m][n];dp[m-1][n-1] map[m-1][n-1] 0?1:Math.abs(map[m-1][n-1]) 1;for (int i n-2; i 0 ; i--) {dp[m-1][i] Math.max(dp[m-1][i1] - map[m-1][i] ,1);}for (int i m-2; i 0 ; i--) {dp[i][n-1] Math.max(dp[i1][n-1] - map[i][n-1] ,1);for (int j n-2; j 0 ; j--) {int right Math.max(dp[i][j1] - map[i][j],1);int down Math.max(dp[i1][j] - map[i][j],1);dp[i][j] Math.min(right,down);}}return dp[0][0];}
}
