leetcode
leetcode 151 ~ 200
地下城游戏

地下城游戏

难度:

标签:

题目描述

恶魔们抓住了公主并将她关在了地下城 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.length
  • n == dungeon[i].length
  • 1 <= m, n <= 200
  • -1000 <= dungeon[i][j] <= 1000

代码结果

运行时间: 28 ms, 内存: 18.1 MB

/*
 * 思路：
 * 1. 使用与Java代码相同的反向动态规划策略。
 * 2. 因为Java Stream API不适合处理二维数组的DP问题，
 *    所以使用传统的for循环来实现。
 */
public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        Arrays.stream(dp).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));
        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] = Math.max(minHealth, 1);
            }
        }
        return dp[0][0];
    }
}

解释

方法:

该题解使用动态规划的思路来解决问题。我们定义状态 dp[i][j] 表示从坐标 (i,j) 到终点所需的最小生命值。状态转移方程为：dp[i][j] = max(min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 1)。我们从右下角开始，倒着往左上角推导状态。最后返回 dp[0][0] 即为所需的最小初始生命值。

时间复杂度:

O(m*n)

空间复杂度:

O(m*n)

代码细节讲解

🦆
为什么在动态规划中的状态转移方程中使用`max(min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 1)`，这里的逻辑是如何确定的？
▷
这个状态转移方程的核心在于确保任何时候角色的生命值至少为1以继续游戏。`min(dp[i+1][j], dp[i][j+1])` 代表从当前位置 (i, j) 向右或向下走时所需的最小生命值。从 (i, j) 出发时，角色会收到 `dungeon[i][j]` 的影响，这可能是正的（增加生命值）或负的（减少生命值）。因此，角色在 (i, j) 位置结束时至少需要的生命值是 `min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]`。然而，无论 `dungeon[i][j]` 是正是负，角色的生命值不能小于1，因此使用 `max(..., 1)` 确保至少为1。
🦆
在初始化最后一行和最后一列的状态时，为什么选择的初始条件是`max(dp[相邻位置] - dungeon[当前位置], 1)`？
▷
在初始化最后一行和最后一列时，这些位置只有一个方向可以移动（最后一行只能向右移动，最后一列只能向下移动）。因此，初始化这些位置的状态时，只需要考虑单一方向上的相邻位置。对于这些边界位置，其所需的最小生命值计算方式与其他位置类似：从当前位置到目标位置（终点）所需的生命值减去当前位置的地牢值，同时确保结果不小于1。这样可以确保角色从这些边界位置开始时，不论地牢值的影响如何，都有足够的生命值至少为1继续游戏。
🦆
如何理解动态规划数组dp中每一个位置的含义？即dp[i][j]代表的具体是什么？
▷
在这个问题中，动态规划数组dp[i][j]表示从位置(i, j)到目标位置（通常是右下角）所需要的最小生命值。这个值保证了从任何一个位置开始，角色都可以到达终点且在任何时刻生命值都不会低于1。这样的设置帮助我们从终点反向推导出起点所需的最小生命值，即dp[0][0]。
🦆
在逆向填充dp数组时，为何要确保`dp[i][j]`的值不小于1，即使用`max(..., 1)`的原因是什么？
▷
在地下城游戏中，角色的生命值如果降至0或更低表示游戏结束。因此，为了保证角色能够从任何位置(i, j)安全地到达终点，我们需要保证在任何时刻角色的生命值至少为1。这是为了避免角色因生命值耗尽而无法继续游戏。使用 `max(..., 1)` 确保即使计算得到的生命值需求是0或负数，我们也会将其调整至最低有效生命值1。

相关问题

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

 

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

 

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

 

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

摘樱桃

给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：

  • 0 表示这个格子是空的，所以你可以穿过它。
  • 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
  • -1 表示这个格子里有荆棘，挡着你的路。

请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：

  • 从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；
  • 当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
  • 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；
  • 如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。

 

示例 1：

输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]]
输出：5
解释：玩家从 (0, 0) 出发：向下、向下、向右、向右移动至 (2, 2) 。
在这一次行程中捡到 4 个樱桃，矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。
然后，玩家向左、向上、向上、向左返回起点，再捡到 1 个樱桃。
总共捡到 5 个樱桃，这是最大可能值。

示例 2：

输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
输出：0

 

提示：

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 50
  • grid[i][j] 为 -1、0 或 1
  • grid[0][0] != -1
  • grid[n - 1][n - 1] != -1
二叉搜索树迭代器最大数