地牢游戏解说

Question

地牢游戏被描述为：

恶魔抓住了公主(P)，并将她囚禁在地牢右下角。地牢由M个房间组成，布置在一个2D网格中。我们英勇的骑士(K)最初的位置是在左上角的房间，必须战斗他的方式通过地牢，以拯救公主。

骑士有一个由正整数表示的初始生命点。如果在任何时候他的健康点下降到0或以下，他立即死亡。

其中一些房间被恶魔守卫，因此骑士进入这些房间时失去生命(负数)；其他房间要么是空的(0)，要么是包含魔法球来增加骑士的生命(正整数)。

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

编写一个函数来确定骑士的最低初始健康状况，以便他能够拯救公主。

例如，给定下面的地牢，骑士的初始健康必须至少为7，如果他遵循最优路径->右->向下->下降。

备注：

骑士的健康没有上限。任何房间都可以包含威胁或权力，甚至是骑士进入的第一个房间和公主被囚禁的右下角的房间。

示例：

dungeon = [[-2,  -3,  4],
           [-6, -15,  0],
           [10,  25, -6]]

答：8

代码解决方案是：

def dungeonGame(dungeon):
    dp = [float("inf") for _ in dungeon[0]] 
    dp[-1] = 1 

    for i in reversed(range(len(dungeon))):
        dp[-1] = max(dp[-1] - dungeon[i][-1], 1)
        for j in reversed(range(len(dungeon[i]) - 1)):
            min_HP_on_exit = min(dp[j], dp[j + 1])
            dp[j] = max(min_HP_on_exit - dungeon[i][j], 1)

    return dp[0]

有人能解释一下上面的解决方案是如何工作的吗？为什么只有dp 3有提供的示例？是否因为只需要三个步骤，不包括起居室和完工室？为什么它在相邻的dp上得到最小值，然后得到最大值？另外，为什么最后一列似乎没有被考虑到，因为dungeoni，其中j只上升到1(以给定的例子矩阵)。我知道这个解决方案写得很好，只是想弄清楚它是如何把所有的路径都考虑进去的。

Answer 1

该算法从右下角返回，然后向左再向上，为沿途的每一步找到最佳得分。我建议您用笔和纸来执行该算法，在此过程中写下i、j和dp的当前值。这应该能把事情弄清楚。

(开始)：No i和no j，dp = inf inf 1

达到右下角后，您至少需要1 HP才能获胜。

(进入第一个循环后)：i=2，dp = inf 7。

你需要7健康，以生存-6的右下角本身。

(进入内环后)：i=2，j=1，dp = inf 1 7

如果你是在最下面的中心广场，最起码的1点生命值就足以撑过那个广场的+25，并到达至少需要7点的相邻广场，以此类推。

这是在向右(存储在中间结果的下一个元素dp[j + 1])和向下( dp[j] )之间进行选择的关键路线。

min_HP_on_exit = min(dp[j], dp[j + 1])

中间结果只有三个元素，因为移动规则(只有向右和向下移动)和对角线为3的地牢，最多只有3个位置可以在任意次数的移动之后到达。

每次求解者向上移动一条线时，最后一列将作为特例在这里处理：

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

为什么？它不同于其他列，因为你不能向右移动，只能向下移动。