算法题：地下城游戏
核心思路
动态规划实现
dp[i][j] 为到达 i, j 位置时所需的最小血量。因为我们反向推算，从终点 (m-1, n-1) 开始，那么终点的血量就应该是 max(1, 1 - grid[m-1][n-1])，也就是说，如果终点的伤害值大于1，那么血量就要至少是1；否则，血量应该足够补偿这个伤害。i, j，我们要看从右边或下边走过来时，所需的血量是多少，确保自己能在进入该位置时不死。最终，我们的目标就是找到 (0, 0) 位置时的血量。代码实现
public class DungeonGame {
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
// dp[i][j] 表示到达(i, j)位置所需的最小血量
int[][] dp = new int[m + 1][n + 1];
// 初始化 dp，终点右下角和右下角右方，都是非常高的数
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = Integer.MAX_VALUE;
}
}
// 终点必须至少有1血量
dp[m][n - 1] = dp[m - 1][n] = 1;
// 从右下角反向推算最小血量
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int minHealth = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = minHealth <= 0 ? 1 : minHealth;
}
}
return dp[0][0];
}
}
dp 来记录每个位置需要的最小血量。接着，初始化右下角的两个边界（因为是从终点开始计算的）。然后，逐步通过动态规划的方式反向推算每个位置的最小血量。解释代码逻辑
初始化：在代码开始时，我们将 dp数组初始化为最大值Integer.MAX_VALUE。这是为了避免在计算过程中出现“未初始化”的情况。而且，我们确保终点(m, n)的血量至少为1。推算血量：从终点 (m-1, n-1)开始，逐步计算每个格子的最小血量。我们通过Math.min(dp[i + 1][j], dp[i][j + 1])选择从哪个方向（下方或者右方）走来能得到更低的血量。然后，减去当前格子的伤害值，得到当前格子的最小血量。保证不死：如果计算出来的最小血量小于或等于零，我们就把血量设置为1，因为角色不可能血量为零或者负数。
时间复杂度
小结
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
