#yyds干货盘点# LeetCode程序员面试金典：地下城游戏

1.简述：

恶魔们抓住公主，把她关在地下城dungeon 的 右下角 。地下城是由 m x n 由房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 在房间里，他必须穿过地下城，通过对抗恶魔来拯救公主。

骑士的初始健康点是正整数。如果他的健康点在某一时刻下降到 0 或以下，他会立即死亡。

有些房间由恶魔守卫，所以骑士进入这些房间时会失去健康点(如果房间里的值是负整数，说明骑士会失去健康点)；其他房间要么是空的(房间里的价值是 0)，或者包含增加骑士健康点数的魔法球(如果房间里的值是正整数，说明骑士会增加健康点数)。

骑士决定每次只救公主，以便尽快救公主 向右 或 向下 移动一步。

返回以确保骑士能够拯救公主所需的最低初始健康点。

注：任何房间都可能对骑士的健康点构成威胁，或增加骑士的健康点，包括骑士进入的左上角房间和公主监禁的右下角房间。

示例 1：

输入：dungeon = [[-2，-3，3]，[-5，-10，1]，[10，30，-5]

输出：7

说明:如果骑士遵循最佳路径:右: -> 右 -> 下 -> 下 ，骑士的初始健康点至少是 7 。

示例 2：

输入：dungeon = [[0]]

输出：1

2.实现代码：

class Solution {    public int calculateMinimumHP(int[][] dungeon) {        int n = dungeon.length, m = dungeon[0].length;        int[][] dp = new int[n + 1][m + 1];        for (int i = 0; i <= n; ++i) {            Arrays.fill(dp[i], Integer.MAX_VALUE);        }        dp[n][m - 1] = dp[n - 1][m] = 1;        for (int i = n - 1; i >= 0; --i) {            for (int j = m - 1; j >= 0; --j) {                int minn = Math.min(dp[i + 1][j], dp[i][j + 1]);                dp[i][j] = Math.max(minn - dungeon[i][j], 1);            }        }        return dp[0][0];    }}