0174-地下城游戏
恶魔们抓住了公主并将她关在了地下城 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
方法一:动态规划
思路及算法
几个要素:「$M \times N$ 的网格」「每次只能向右或者向下移动一步」,让人很容易想到该题使用动态规划的方法。
但是我们发现,如果按照从左上往右下的顺序进行动态规划,对于每一条路径,我们需要同时记录两个值。第一个是「从出发点到当前点的路径和」,第二个是「从出发点到当前点所需的最小初始值」。而这两个值的重要程度相同,参看下面的示例:
{:width=”80%”}
从 $(0,0)$ 到 $(1,2)$ 有多条路径,我们取其中最有代表性的两条:
{:width=”80%”}
绿色路径「从出发点到当前点的路径和」为 $1$,「从出发点到当前点所需的最小初始值」为 $3$。
蓝色路径「从出发点到当前点的路径和」为 $-1$,「从出发点到当前点所需的最小初始值」为 $2$。
我们希望「从出发点到当前点的路径和」尽可能大,而「从出发点到当前点所需的最小初始值」尽可能小。这两条路径各有优劣。
在上图中,我们知道应该选取绿色路径,因为蓝色路径的路径和太小,使得蓝色路径需要增大初始值到 $4$ 才能走到终点,而绿色路径只要 $3$ 点初始值就可以直接走到终点。但是如果把终点的 $-2$ 换为 $0$,蓝色路径只需要初始值 $2$,绿色路径仍然需要初始值 $3$,最优决策就变成蓝色路径了。
因此,如果按照从左上往右下的顺序进行动态规划,我们无法直接确定到达 $(1,2)$ 的方案,因为有两个重要程度相同的参数同时影响后续的决策。也就是说,这样的动态规划是不满足「无后效性」的。
于是我们考虑从右下往左上进行动态规划。令 $\textit{dp}[i][j]$ 表示从坐标 $(i,j)$ 到终点所需的最小初始值。换句话说,当我们到达坐标 $(i,j)$ 时,如果此时我们的路径和不小于 $\textit{dp}[i][j]$,我们就能到达终点。
这样一来,我们就无需担心路径和的问题,只需要关注最小初始值。对于 $\textit{dp}[i][j]$,我们只要关心 $\textit{dp}[i][j+1]$ 和 $\textit{dp}[i+1][j]$ 的最小值 $\textit{minn}$。记当前格子的值为 $\textit{dungeon}(i,j)$,那么在坐标 $(i,j)$ 的初始值只要达到 $\textit{minn}-\textit{dungeon}(i,j)$ 即可。同时,初始值还必须大于等于 $1$。这样我们就可以得到状态转移方程:
$$
\textit{dp}[i][j] = \max(\min(\textit{dp}[i+1][j], \textit{dp}[i][j + 1]) - \textit{dungeon}(i, j), 1)
$$
最终答案即为 $\textit{dp}[0][0]$。
边界条件为,当 $i=n-1$ 或者 $j=m-1$ 时,$\textit{dp}[i][j]$ 转移需要用到的 $\textit{dp}[i][j+1]$ 和 $\textit{dp}[i+1][j]$ 中有无效值,因此代码实现中给无效值赋值为极大值。特别地,$\textit{dp}[n-1][m-1]$ 转移需要用到的 $\textit{dp}[n-1][m]$ 和 $\textit{dp}[n][m-1]$ 均为无效值,因此我们给这两个值赋值为 $1$。
代码
1 | class Solution { |
1 | class Solution { |
1 | class Solution: |
1 | int calculateMinimumHP(int** dungeon, int dungeonSize, int* dungeonColSize) { |
1 | func calculateMinimumHP(dungeon [][]int) int { |
复杂度分析
时间复杂度:$O(N \times M)$,其中 $N,M$ 为给定矩阵的长宽。
空间复杂度:$O(N \times M)$,其中 $N,M$ 为给定矩阵的长宽,注意这里可以利用滚动数组进行优化,优化后空间复杂度可以达到 $O(N)$。