中国建设银行官网站下载中心,网站和软件有什么区别,如何在服务器上发布网站,网站的推广平台有哪些一片丹心图报国#xff0c;两行清泪为忠家。——于谦 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康…一片丹心图报国两行清泪为忠家。——于谦 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。 示例 1 输入dungeon [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出7
解释如果骑士遵循最佳路径右 - 右 - 下 - 下 则骑士的初始健康点数至少为 7 。
示例 2
输入dungeon [[0]]
输出1提示
m dungeon.lengthn dungeon[i].length1 m, n 200-1000 dungeon[i][j] 1000 public int calculateMinimumHP(int[][] dungeon) {if (dungeon null || dungeon.length 0 || dungeon[0].length 0) {return 0;}int m dungeon.length;int n dungeon[0].length;int[][] dp new int[m][n];dp[m - 1][n - 1] Math.max(1, 1 - dungeon[m - 1][n - 1]);// 初始化最后一列for (int i m - 2; i 0; i--) {dp[i][n - 1] Math.max(dp[i 1][n - 1] - dungeon[i][n - 1], 1);}// 初始化最后一行for (int j n - 2; j 0; j--) {dp[m - 1][j] Math.max(dp[m - 1][j 1] - dungeon[m - 1][j], 1);}// 逆向计算 dp 值for (int i m - 2; i 0; i--) {for (int j n - 2; j 0; j--) {int min_hp_on_exit Math.min(dp[i 1][j], dp[i][j 1]);dp[i][j] Math.max(min_hp_on_exit - dungeon[i][j], 1);}}return dp[0][0];
}
