174.地下城游戏——LeetCode
题目
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7
解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
解题思路
这个问题是一个典型的动态规划问题，我们需要找到从左上角到右下角的路径上，骑士所需的最小初始健康点数，使得在任何时候骑士的健康点数都不会降到0或以下。
动态规划的状态转移方程应该是这样的：
设 dp[i][j] 表示到达房间 (i, j) 时所需的最小生命值。由于骑士可以选择向下或向右移动，dp[i][j] 可以通过 dp[i+1][j]（从上方房间来）或 dp[i][j+1]（从左侧房间来）计算得出。我们需要考虑以下两种情况：
- 如果从上方房间
(i+1, j)来，骑士需要在当前房间(i, j)至少剩余dp[i+1][j] - dungeon[i+1][j]生命值。 - 如果从左侧房间
(i, j+1)来，骑士需要在当前房间(i, j)至少剩余dp[i][j+1] - dungeon[i][j+1]生命值。
我们需要取这两种情况中的较大者，因为骑士需要在进入房间前保证足够的生命值。然后，我们需要考虑当前房间 (i, j) 的效果 dungeon[i][j]，如果 dungeon[i][j] 是负数，骑士将失去生命值。
因此，状态转移方程为：
解题过程
-
初始化
dp数组，其大小与dungeon相同。 -
设置右下角的
dp值，根据房间值决定初始健康点数。 -
从右下角开始向上和向左遍历
dungeon，填充dp数组。 -
对于每个格子
(i, j)，计算从右边(i, j+1)和下面(i+1, j)到达的最小健康点数，并取较小者。 -
从计算结果中减去当前格子的值，确保结果至少为1（因为骑士不能有0或负的健康点数）。
-
循环结束后，
dp[0][0]就是所需的最小初始健康点数。
复杂度
-
时间复杂度：O(m×n)O(m×n)，其中
m和n分别是dungeon的行数和列数。我们需要遍历整个dungeon。 -
空间复杂度：O(m×n)O(m×n)，用于存储动态规划表
dp。如果只存储一行或一列的状态，可以优化到 O(min(m,n))O(min(m,n))。
Code
class Solution {public int calculateMinimumHP(int[][] dungeon) {final int m = dungeon.length, n = dungeon[0].length;int[][] dp = new int[m][n];// 初始化dp数组的右下角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(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);}for (int j = n - 2; j >= 0; j--) {dp[m - 1][j] = Math.max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);}// 动态规划填表for (int i = m - 2; i >= 0; i--) {for (int j = n - 2; j >= 0; j--) {// 取右边和下边的最小值，并减去当前房间的值dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);}}return dp[0][0];}
}