地下城游戏

难度: Hard

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

Submission

运行时间: 28 ms

内存: 18.1 MB

class Solution:

    # 动态规划：状态的定义，状态的初始，状态的转移；状态需要有无后向性
    # 注释掉的这种解法不满足无后向性，所以不行
    # def minHP(self, last_min, hp, cost):
    #     hp += cost
    #     if hp < last_min:
    #         last_min = hp
    #     return last_min, hp

    # def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
    #     # f(i, j) (0, 0)-(i, j)过程中最低的hp值和路径和
    #     m, n = len(dungeon), len(dungeon[0])
    #     dp = [[(0, 0)] * n for _ in range(m)]
    #     dp[0][0] = (dungeon[0][0], dungeon[0][0])
    #     for i in range(1, m):
    #         dp[i][0] = self.minHP(dp[i-1][0][0], dp[i-1][0][1], dungeon[i][0])
    #     for j in range(1, n):
    #         dp[0][j] = self.minHP(dp[0][j-1][0], dp[0][j-1][1], dungeon[0][j])
    #     for i in range(1, m):
    #         for j in range(1, n):
    #             left_last_min, left_hp =  self.minHP(dp[i][j-1][0], dp[i][j-1][1], dungeon[i][j])
    #             up_last_min, up_hp =  self.minHP(dp[i-1][j][0], dp[i-1][j][1], dungeon[i][j])
    #             if left_last_min > up_last_min:
    #                 dp[i][j] = (left_last_min, left_hp)
    #             else:
    #                 dp[i][j] = ( up_last_min, up_hp)
    #     print(dp)
    #     return max(1, -dp[-1][-1][0]+1)

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

Explain

该题解使用动态规划的思路来解决问题。我们定义状态 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)

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        # 定义状态数组 dp，dp[i][j] 表示从 (i,j) 到终点所需的最小生命值
        dp = [[0] * n for _ in range(m)]
        
        # 初始化最后一个状态
        dp[m-1][n-1] = max(1 - dungeon[m-1][n-1], 1)
        
        # 初始化最后一列的状态
        for i in range(m-2, -1, -1):
            dp[i][n-1] = max(dp[i+1][n-1] - dungeon[i][n-1], 1)
        
        # 初始化最后一行的状态
        for j in range(n-2, -1, -1):
            dp[m-1][j] = max(dp[m-1][j+1] - dungeon[m-1][j], 1)
        
        # 倒着递推每个状态的值
        for i in range(m-2, -1, -1):
            for j in range(n-2, -1, -1):
                dp[i][j] = max(min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 1)
        
        # 返回左上角所需的最小生命值             
        return dp[0][0]

Explore

这个状态转移方程的核心在于确保任何时候角色的生命值至少为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。

在初始化最后一行和最后一列时，这些位置只有一个方向可以移动（最后一行只能向右移动，最后一列只能向下移动）。因此，初始化这些位置的状态时，只需要考虑单一方向上的相邻位置。对于这些边界位置，其所需的最小生命值计算方式与其他位置类似：从当前位置到目标位置（终点）所需的生命值减去当前位置的地牢值，同时确保结果不小于1。这样可以确保角色从这些边界位置开始时，不论地牢值的影响如何，都有足够的生命值至少为1继续游戏。

在这个问题中，动态规划数组dp[i][j]表示从位置(i, j)到目标位置（通常是右下角）所需要的最小生命值。这个值保证了从任何一个位置开始，角色都可以到达终点且在任何时刻生命值都不会低于1。这样的设置帮助我们从终点反向推导出起点所需的最小生命值，即dp[0][0]。

在地下城游戏中，角色的生命值如果降至0或更低表示游戏结束。因此，为了保证角色能够从任何位置(i, j)安全地到达终点，我们需要保证在任何时刻角色的生命值至少为1。这是为了避免角色因生命值耗尽而无法继续游戏。使用 `max(..., 1)` 确保即使计算得到的生命值需求是0或负数，我们也会将其调整至最低有效生命值1。