174. 地下城游戏

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/dungeon-game

题目

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。咱们勇敢的骑士（K）最后被安置在左上角的房间里，他必须穿过地下城并通过反抗恶魔来援救公主。

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

有些房间由恶魔守卫，因而骑士在进入这些房间时会失去衰弱点数（若房间里的值为负整数，则示意骑士将损失衰弱点数）；其余房间要么是空的（房间里的值为 0），要么蕴含减少骑士衰弱点数的魔法球（若房间里的值为正整数，则示意骑士将减少衰弱点数）。

为了尽快达到公主，骑士决定每次只向右或向下挪动一步。

编写一个函数来计算确保骑士可能援救到公主所需的最低初始衰弱点数。

例如，思考到如下布局的地下城，如果骑士遵循最佳门路 右 -> 右 -> 下 -> 下，则骑士的初始衰弱点数至多为 7。

阐明:

• 骑士的衰弱点数没有下限。
• 任何房间都可能对骑士的衰弱点数造成威逼，也可能减少骑士的衰弱点数，包含骑士进入的左上角房间以及公主被监禁的右下角房间。

解题思路

思路：动静布局

先说须要留神的点：【题目中曾经阐明，壮士只能向右，向下挪动】，【如果壮士的衰弱点数在某一时刻降至 0 或以下，他会立刻死亡】。

在这道题中，咱们要应用反向动静布局。如果抉择应用正向的动静布局，会呈现 dp 值更新艰难的问题。

大抵阐明下这个状况，假如有以下二维网格：

当初假如，依照以下的走法来走向右下角的指标起点：

在这里，咱们首先须要记录路线的【门路和】和【最小初始化值】：

• 先看下面红色的路线：从左上角 (0, 0) 到 (1, 2) 时，【门路和】为 2，【最小初始化值】为 4；
• 再看绿色的路线：从左上角 (0, 0) 到 (2, 1) 时，【门路和】为 1，【最小初始化值】为 3。

后面曾经说过须要留神的点，壮士的血量值必须要时刻大于 0。那么，咱们的路线布局，就必须要保障【门路和】要尽可能的大，而【最小初始化值】则尽可能的小。

在下面的示例当中，咱们最终会抉择红色的路线，因为当抉择红色路线时，【最小初始化值】为 4 的状况下，是可能走到起点的。而如果抉择绿色路线，要想走到起点，因为【门路和】较小，这个时候要增大【最小初始化值】至 5 能力平安达到。

然而，如果起点地位（也就是右下角坐标 (2, 2)）的值 -5 变为大于或等于 0 的数值时，这个时候，状况就会发生变化。当起点值发生变化之后，红色路线【最小初始化值】还是 4，然而绿色路线【最小初始化值】将只须要 3。

依据下面的剖析，咱们能够发现，如果抉择正向的动静布局时，无奈满足动静布局的【无后效性】。那么咱们这个时候思考反向的动静布局。

状态定义

设 dp[i][j] 示意从 (i, j) 达到起点所需的最小初始化值。

状态转移

咱们采纳反向动静布局，那么在这里，dp[i][j] 只须要关怀 dp[i][j+1] 和 dp[i+1][j] 的最小值，而以后点的值为 dungeon[i][j]。在这里，初始值还必须大于等于 1，那么此时状态转移方程为：

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

咱们最终需要求的是 dp[0][0]。

状态初始化

先思考边界问题:

• i = m - 1 和 j = n - 1 时，dp[i][j+1] 和 dp[i+1][j] 会呈现越界问题，将两者值设为 1。也就是：dp[m-1][n] = 1，dp[m][n-1] = 1

具体的代码实现如下。

代码实现

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m = len(dungeon)
        n = len(dungeon[0])

        dp = [[float('inf')] * (n+1) for _ in range(m+1)]

        # 初始化值
        dp[m-1][n] = 1
        dp[m][n-1] = 1

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                dp[i][j] = max(min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j], 1)
        
        return dp[0][0]

实现后果

欢送关注

公众号【书所集录】