174. 地下城游戏

🔴   🔖  数组 动态规划 矩阵  🔗 力扣 LeetCode

题目

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).

To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Return the knight 's minimum initial health so that he can rescue the princess.

Note that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Example 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]

Output: 7

Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

Example 2:

Input: dungeon = [[0]]

Output: 1

Constraints:

• m == dungeon.length
• n == dungeon[i].length
• 1 <= m, n <= 200
• -1000 <= dungeon[i][j] <= 1000

题目大意

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

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

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

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

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

注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

解题思路

• 错误的做法：

  • 这道题对 dp 数组的定义比较有意思，按照常理，dp 数组的定义应该是：从左上角 (0, 0) 走到 (i, j) 至少需要 dp[i][j] 的生命值。

  • 但是如果只知道「能够从左上角到达 (i, j) 的最小生命值」，但并不知道「到达 (i, j) 时的生命值」，就无法进行状态转移。例如下面这种情况：

  

  • 图中，骑士救公主的最优路线是按照图中蓝色的线走到 B，最后走到 A ，这样初始血量只需要 1 ；如果走黄色箭头这条路，先走到 C 然后走到 A，初始血量至少需要 6。
  • 因为骑士走到 B 的时候生命值为 11，而走到 C 的时候生命值依然是 1。所以虽然骑士走到 B 和 C 的最少初始血量都是 1，但是最后需要选择从 B 走到 A 。
  • 所以说，之前对 dp 数组的定义是错误的，信息量不足，算法无法做出正确的状态转移。

• 正确的做法：

  • 正确的做法需要反向思考，dp 数组的定义为：从 (i, j) 到达终点（右下角）所需的最少生命值是 dp[i][j]。
  • 从右下角开始逆向遍历，通过 dp[i][j+1] 和 dp[i+1][j] 推导出 dp[i][j]，最后返回 dp[0][0]。
  • 状态转移方程：dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])，其中 dp[i+1][j] 和 dp[i][j+1] 分别表示从下方和右方到达 (i, j) 的最小生命值，然后减去当前格子所需的生命值，最后取最大值为当前格子所需的最小生命值。
  • 初始化边界：为了处理边界情况，需要在右下角、最后一行、最后一列的位置初始化。

复杂度分析

• 时间复杂度: O(m * n)，遍历整个二维数组。
• 空间复杂度: O(m * n)，使用了一个二维数组来存储中间状态。

代码

/**
 * @param {number[][]} dungeon
 * @return {number}
 */
var calculateMinimumHP = function (dungeon) {
	const m = dungeon.length;
	const n = dungeon[0].length;
	// 初始化 dp 数组
	const dp = new Array(m).fill(0).map(() => new Array(n).fill(-1));
	for (let i = m - 1; i >= 0; i--) {
		for (let j = n - 1; j >= 0; j--) {
			if (i == m - 1 && j == n - 1) {
				// 处理右下角的边界情况
				dp[i][j] = Math.max(1, 1 - dungeon[i][j]);
			} else if (i == m - 1) {
				// 处理最后一行的边界情况
				dp[i][j] = Math.max(1, dp[i][j + 1] - dungeon[i][j]);
			} else if (j == n - 1) {
				// 处理最后一列的边界情况
				dp[i][j] = Math.max(1, dp[i + 1][j] - dungeon[i][j]);
			} else {
				dp[i][j] = Math.max(
					1,
					Math.min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j]
				);
			}
		}
	}
	return dp[0][0];
};

相关题目

题号	标题	题解	标签	难度
62	不同路径	[✓]	数学 动态规划 组合数学
64	最小路径和	[✓]	数组 动态规划 矩阵
741	摘樱桃		数组 动态规划 矩阵
2214	通关游戏所需的最低生命值 🔒		贪心 数组
2304	网格中的最小路径代价		数组 动态规划 矩阵
2435	矩阵中和能被 K 整除的路径		数组 动态规划 矩阵
2510	检查是否有路径经过相同数量的 0 和 1 🔒		数组 动态规划 矩阵