What is the main strategy to solve Dungeon Game efficiently?

Use reverse state transition dynamic programming from the princess back to the knight to calculate the minimum initial health required.

Can we optimize space usage in Dungeon Game DP solution?

Yes, instead of a full m x n table, a single row array can store current minimum health values and be updated in-place.

Why must health never drop below 1 in this problem?

The knight dies immediately if health reaches zero or below, so the DP must ensure a minimum of 1 at every step.

How do demons and health orbs affect the DP calculation?

Negative values decrease required health in previous cells, while positive values reduce the minimum initial health needed, impacting the DP recurrence.

Is Dungeon Game considered a state transition dynamic programming problem?

Yes, it is a classic state transition DP problem where each cell's required health depends on the minimum of its right and bottom neighbors.

#174

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

地下城游戏

恶魔们抓住了公主并将她关在了地下城 dungeon 的右下角。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。有些房…

数组动态规划矩阵

题目描述

恶魔们抓住了公主并将她关在了地下城 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

lightbulb

解题思路

方法一：动态规划

我们定义 $dp[i][j]$ 表示从 $(i, j)$ 到终点所需的最小初始值，那么 $dp[i][j]$ 的值可以由 $dp[i+1][j]$ 和 $dp[i][j+1]$ 得到，即：

dp[i][j] = \max(\min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 1)

初始时 $dp[m][n-1]$ 和 $dp[m-1][n]$ 都为 $1$ ，其他位置的值为最大值。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为地牢的行数和列数。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[inf] * (n + 1) for _ in range(m + 1)]
        dp[m][n - 1] = dp[m - 1][n] = 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
        return dp[0][0]

speed

复杂度分析

指标	值
时间	complexity is O(m _n) due to visiting each cell once for DP calculation. Space complexity is O(n) if optimizing to a single row, otherwise O(m_ n) for the full DP table.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect discussion of reverse DP and minimum health calculations.
question_mark
Check if candidate optimizes space from O(m*n) to O(n).
question_mark
Look for correct handling of edge cases with demons and health orbs.

warning

常见陷阱

外企场景

error
Forgetting that health cannot drop below 1 at any cell.
error
Attempting forward DP from start without reverse reasoning leads to incorrect min health.
error
Mishandling last row or column calculations and off-by-one errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing diagonal moves changes the DP recurrence and state transitions.
arrow_right_alt
Variable health regeneration rates in positive cells introduce different state updates.
arrow_right_alt
Multiple princesses require multi-target DP or BFS with min health tracking.

help

常见问题

外企场景

继续练习

#221 最大正方形 #85 最大矩形 #64 最小路径和