0174 - Dungeon Game
题干
破题
绝对标准地 Hard 难度的问题。
给一个二维的地图，从左上角走到右下角，看起来非常像之前做过的譬如 0085 - Maximal Rectangle 这样的题目，只需要从上到下地逐行扫描，计算从起点到每一行的每个位置的子问题的解，直到最后一行的最后一个位置。
但是对于本题这样做是不行的，因为一般到某个位置的路线有两条，一条是从上到下的，一条是从左到右的，而有两个指标用来选择最小生命值的路线，一个是到当前位置为止整个路径上出现过的路径和的最小值，另一个是到当前位置的路径和。这两个指标可能是矛盾的，比如有一条路线的最小值较大但是路径和较小，导致选择该路线最终在后面得到了较小的最小值，从而得到了不正确的结果。
换句话说，前面的子问题的路线选择受后面位置数值的影响，这个 DP 的解法存在后效性，因此这个解法是不能成立的。
这样问题就陷入了困局，实际上我花了几天的时间去考虑这个题，终于发现我们可以从终点开始做 DP 这样就避开了后效性的问题，于是引入了新的 DP 思路：后效翻转 。
对于这道题来说，子问题变成从前面的位置到终点的最小生命值，这样从后向前找，路线的选择是确定的，只需要比较两条路线：下方和右方对应的解，选较大的即可，而当前位置子问题的解则是比较
- 后面的解加上当前位置值；
- 当前位置的值，取这两个的最小值
顺带一讲，这个解应该是路径上的最小值，而路径的选择是让这个路径最小值取到最大，这样才可以付出最小生命。最后的最小生命就是把这个最小值取反，比较它与零的大小，取一个最大值，把结果加上 1 ，这样保证最后至少有一点生命值。
解①迭代版本：
或者说 BFS，比起递归版本，这个版本通常有更多地细节去深入。
这个解法的复杂之处在于需要考虑下受地图矩形的长度和宽度两个因素限制的坐标位置，特别是如果我们想要用一维数组来存储子问题解的话。
计算的整个过程是从终点倒退回起点，计算每一步可到位置的子问题解，就如下图所示：
灰色线连起来的区域就是每一步可能到达的位置，这里用步数作为控制流程的变量，并为了方便以终点为原点建立坐标系，等到访问 dungeon 数组（以下简写作 $D$ ）时再把坐标转换为以左上角为原点的坐标系。
这样地话，对于 $m$ 行 $n$ 列的 $D$ 数组 假设当前步数是 $l$ ，那么
能够到达的最大的高度 $h=\min(m,l)$ ，最大宽度 $w=\min(n,l)$ 。
因此在当前步数的从左下到右上的可达范围里
左下位置 $(x_0,y_0): (l-w+1,w)$ ，右上位置 $(x_1,y_1): (h, l-h+1)$ 。
这样的话，每一步的位置范围就是从 $x_0 \rightarrow x_1$ ，记录下它的差 $d_\text{max} = x_1-x_0$ ，可以用来指示当前步数最后一个位置的在一维数组里的下标。
由于每步的位置数并不相同，因此交替使用两个一维的数组（$\text{low}_1$ 和 $\text{low}_0$）来存储当前步数和之前步数的子问题解，而解的计算要根据所处位置分为三个阶段、四种情况。三个阶段是随着步数的增加会出现的，矩形长宽都没有限制的前场、较短一维限制而较长一维没有限制的中场，以及两个维度都被限制的后场。
1. 矩形前场
矩形前场就是在从终点开始的扫描过程中，随着步数增加，$h$ 和 $w$ 增加的情况。此时最左下角只能从它的右方得到，右上角只能从它的下方得到，其余位置都可以从两边得到。
\[\text{low}_1[i] \leftarrow \left \{\begin{array}{l} \text{low}_0[0]& (i=0) \\ \text{low}_0[d_\text{max}-1] &(i=d_\text{max})\\ \left \{\begin{array}{l} \text{low}_0[d-1]\\ \text{low}_0[d] \end{array} \right. &(0\lt i\lt d_\text{max}) \end{array} \right.\]2. 宽矩形中场
所谓中场，就是随着步数增加，$d_\text{max}$ 却保持不变的阶段，是在步数超过较短一维的长度时进入而在步数达到较长一维的长度时退出的一个阶段。 \(\text{low}_1[i] \leftarrow \left \{\begin{array}{l} \text{low}_0[0]& (i=0) \\ \left \{\begin{array}{l} \text{low}_0[d-1]\\ \text{low}_0[d] \end{array} \right. &(0\lt i\leqslant d_\text{max}) \end{array} \right.\)
3. 高矩形中场
\(\text{low}_1[i] \leftarrow \left \{\begin{array}{l} \text{low}_0[d_\text{max}-1] &(i=d_\text{max})\\ \left \{\begin{array}{l} \text{low}_0[d]\\ \text{low}_0[d+1] \end{array} \right. &(0\leqslant i\lt d_\text{max}) \end{array} \right.\)
4. 矩形后场
后场就是当中场结束时，也就是步长超过较长一维时进入的阶段。
\[\text{low}_1[i] \leftarrow \left \{\begin{array}{l} \text{low}_0[d]\\ \text{low}_0[d+1] \end{array} \right. &(0\leqslant i\leqslant d_\text{max})\]于是我们便得到了代码。
from typing import List
def solve(dungeon: List[List[int]]) -> int:
m = len(dungeon)
n = len(dungeon[0])
tot = m+n-1
low0 = [dungeon[-1][-1]] * min(m, n)
low1 = [0] * min(m, n)
for l in range(2, tot+1):
h = min(m, l)
w = min(n, l)
x0, y0 = l-w+1, w
x1, y1 = h, l-h+1
d_max = x1-x0
if x0 == 1 and y1 == 1: # 矩形前半场
low1[0] = min(
dungeon[m-x0][n-y0] + low0[0],
dungeon[m-x0][n-y0]
)
low1[d_max] = min(
dungeon[m-x1][n-y1] + low0[l-2],
dungeon[m-x1][n-y1]
)
for d in range(1, d_max):
x, y = x0+d, y0-d
nx = max(low0[d-1], low0[d])
if nx < 0:
low1[d] = dungeon[m-x][n-y] + nx
else:
low1[d] = dungeon[m-x][n-y]
elif x0 == 1: # 宽矩形中间场
low1[0] = min(
dungeon[m-x0][n-y0] + low0[0],
dungeon[m-x0][n-y0]
)
for d in range(1, d_max+1):
x, y = x0+d, y0-d
nx = max(low0[d-1], low0[d])
if nx < 0:
low1[d] = dungeon[m-x][n-y] + nx
else:
low1[d] = dungeon[m-x][n-y]
elif y1 == 1: # 高矩形中间场 (x0 != 1)
low1[d_max] = min(
dungeon[m-x1][n-y1] + low0[min(m, n)-1],
dungeon[m-x1][n-y1]
)
for d in range(d_max):
x, y = x0+d, y0-d
nx = max(low0[d], low0[d+1])
if nx < 0:
low1[d] = dungeon[m-x][n-y] + nx
else:
low1[d] = dungeon[m-x][n-y]
else: # 矩形后半场
for d in range(d_max+1):
x, y = x0+d, y0-d
nx = max(low0[d], low0[d+1])
if nx < 0:
low1[d] = dungeon[m-x][n-y] + nx
else:
low1[d] = dungeon[m-x][n-y]
low0, low1 = low1, low0
return 1+max(-low0[0], 0)
运行时间：69 ms (beats 81.50%, ~100%, 55 ms)，内存占用：17.5 MB (beats 63.73%, ~100%)。
解②：
或者说 DFS。
在上面的迭代版本或者BFS版本里，不管是分析还是代码都显得有些冗长，这主要是因为我们不愿意直接把判断放在循环里，而要弄清楚所有的过程细节，而对于递归版本，可以很简单地实现。
from functools import cache
from typing import List
def solve(dungeon: List[List[int]]) -> int:
m = len(dungeon)
n = len(dungeon[0])
@cache
def dfs(i, j):
if i >= m or j >= n:
return -float('inf')
if i == m-1 and j == n-1:
return dungeon[i][j]
else:
nx = max(dfs(i+1, j), dfs(i, j+1))
if nx < 0:
return dungeon[i][j] + nx
else:
return dungeon[i][j]
return 1+max(-dfs(0, 0), 0)
运行时间：78 ms (beats 39.60%, ~100%)，内存占用：20.21 MB (beats 5.06%)。
注解
