地下城游戏解决方案说明

Question

地下城游戏描述如下：

恶魔们俘虏了公主并把她囚禁起来 在地牢的右下角。T 地牢由M x N个房间组成，呈二维网格。 我们的英勇骑士（K）最初被安置在左上角的房间里 他必须奋力穿过地牢去救公主。在

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

有些房间有恶魔守卫， 因此骑士在进入这些房间时会失去生命值（负整数）； 其他房间要么是空的（0），要么是包含增加骑士生命值的魔法球（正整数）。在

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

写一个函数来确定骑士的最小初始生命值 这样他就能救公主了。在

例如，给定下面的地牢，初始生命值 骑士必须至少7岁，如果他沿着最佳路径向右->向右->向下->向下-。在

注意事项：

骑士的健康没有上限。 任何房间都可以包含威胁或加电，即使是骑士进入的第一个房间 右下角是公主被囚禁的房间。在

示例：

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

回答：8

代码解决方案是：

^{pr2}$

有人能解释一下上面的解决方案是如何工作的吗？为什么dp只有len 3和所提供的示例？是因为不包括开始和结束房间，只需要3个步骤吗？为什么相邻压差最小，然后最大？另外，为什么最后一列似乎没有被考虑，因为地牢[i][j]，j只上升到1（以给定的矩阵为例）。我知道这个解决方案写得很好，只是想了解它是如何把所有的路径都考虑进去的。在

Answer 1

这个算法从右下角返回，从左到上，找到每一步的最佳分数。我建议你用笔和纸来执行算法，一路上写下I，j和dp的当前值。这应该能让事情变得明朗起来。在

(Start): No i and no j yet, dp = [inf inf 1]

到达右下角后，你至少需要1点生命才能获胜。在

(After entering the first loop): i=2, dp = [inf inf 7].

你需要7点生命值才能生存在右下角的-6点。在

(After entering the inner loop): 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个地方出现。在

每次求解器向上移动一行时，最后一列作为特殊情况处理：

^{pr2}$

为什么？嗯，它和其他列的不同之处在于你不能向右移动，只能向下移动。在