---

0174. 地下城游戏

• 标签：数组、动态规划、矩阵
• 难度：困难

题目链接

• 0174. 地下城游戏 - 力扣

题目大意

描述：

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

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

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

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

要求：

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

说明：

• 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
• $m == dungeon.length$。
• $n == dungeon[i].length$。
• $1 \le m, n \le 200$。
• $-10^{3} \le dungeon[i][j] \le 10^{3}$。

示例：

• 示例 1：

![](https://assets.leetcode.com/uploads/2021/03/13/dungeon-grid-1.jpg)

输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7
解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。

• 示例 2：

输入：dungeon = [[0]]
输出：1

解题思路

思路 1：动态规划（从右下角到左上角）

这道题的关键在于理解：我们需要从右下角开始，逆向思考骑士到达每个位置时所需的最小健康点数。

状态定义：

• 设 $dp[i][j]$ 表示从位置 $(i, j)$ 到达右下角所需的最小初始健康点数。

状态转移方程：

• 对于右下角位置 $(m-1, n-1)$：$dp[m-1][n-1] = \max(1, 1 - dungeon[m-1][n-1])$
• 对于其他位置 $(i, j)$：
  • 如果 $i = m-1$（最后一行）：$dp[i][j] = \max(1, dp[i][j+1] - dungeon[i][j])$
  • 如果 $j = n-1$（最后一列）：$dp[i][j] = \max(1, dp[i+1][j] - dungeon[i][j])$
  • 其他情况：$dp[i][j] = \max(1, \min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])$

算法步骤：

1. 初始化 $dp$ 数组，所有值设为无穷大。
2. 从右下角开始，按照状态转移方程填充 $dp$ 数组。
3. 返回 $dp[0][0]$ 作为答案。

思路 1：代码

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        # dp[i][j] 表示从位置 (i,j) 到达右下角所需的最小初始健康点数
        dp = [[float('inf')] * n for _ in range(m)]
        
        # 从右下角开始逆向填充
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i == m - 1 and j == n - 1:
                    # 右下角：至少需要 1 点健康，如果房间有伤害则增加
                    dp[i][j] = max(1, 1 - dungeon[i][j])
                elif i == m - 1:
                    # 最后一行：只能向右走
                    dp[i][j] = max(1, dp[i][j + 1] - dungeon[i][j])
                elif j == n - 1:
                    # 最后一列：只能向下走
                    dp[i][j] = max(1, dp[i + 1][j] - dungeon[i][j])
                else:
                    # 其他位置：选择向右或向下中所需健康点数更少的路径
                    dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
        
        return dp[0][0]

思路 1：复杂度分析

• 时间复杂度：$O(m \times n)$，其中 $m$ 和 $n$ 分别是地下城的行数和列数。需要遍历整个二维数组一次。
• 空间复杂度：$O(m \times n)$，需要创建一个 $m \times n$ 的二维数组来存储状态。