《Dungeon Game》（地牢游戏）是 LeetCode 上的第 174 题，它是一道经典的动态规划问题。题目描述如下：

题目描述：

表述一个地下城游戏，包含 m x n 个房间，这些房间由二维网格 dungeon 表示。网格中的负整数表示这一位置对骑士的生命值造成的伤害；正整数表示这一位置对骑士的生命值进行的恢复。 骑士初始化时位于左上角的房间，且初始生命值为一个正整数。你必须带领骑士到达右下角的房间（即 dungeon[m-1][n-1]），此时骑士的生命值至少为 1。 编写一个函数来计算确保骑士能够安全到达右下角房间所需的最小初始生命值。

示例：

输入: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] 输出: 7 解释: 初始时骑士的生命值为 7，在路径上骑士的生命值会如下变化: 路径: [1,3,2,1,5,4,7]

解题思路：

1. 逆向思考：从右下角（终点）开始向左上角（起点）进行动态规划。因为我们需要确保骑士到达每个房间时生命值至少为 1。
2. 状态定义：设 dp[i][j] 表示从房间 (i, j) 到终点所需的最小初始生命值。
3. 状态转移方程：
   • 如果 i == m-1 且 j == n-1（即终点），则 dp[i][j] = max(1, 1 - dungeon[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])。
4. 初始化：从右下角开始初始化 dp 数组。
5. 结果：最终 dp[0][0] 即为所需的最小初始生命值。

代码实现（Python）：

def calculateMinimumHP(dungeon): m, n = len(dungeon), len(dungeon[0]) dp = [[0] * n for _ in range(m)]

# 从右下角开始初始化dp数组
for i in range(m-1, -1, -1):
    for j in range(n-1, -1, -1):
        if i == m-1 and j == n-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]

dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] print(calculateMinimumHP(dungeon)) # 输出: 7

解释：

1. 初始化：创建一个 m x n 的 dp 数组，用于存储每个位置到终点所需的最小初始生命值。
2. 逆向遍历：从右下角开始遍历网格，根据状态转移方程计算每个位置的 dp 值。
3. 结果：最终 dp[0][0] 即为从起点到终点所需的最小初始生命值。

通过这种逆向动态规划的方法，可以有效地解决这个地牢游戏问题，确保骑士能够安全到达终点。