0174. Dungeon Game

# 174. Dungeon Game#

## 题目 #

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

Note:

• The knight’s health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

## 题目大意 #

• 骑士的健康点数没有上限。
• 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

## 解题思路 #

• 在二维地图上给出每个格子扣血数，负数代表扣血，正数代表补血。左上角第一个格子是起点，右下角最后一个格子是终点。问骑士初始最少多少血才能走完迷宫，顺利营救位于终点的公主。需要注意的是，起点和终点都会对血量进行影响。每到一个格子，骑士的血都不能少于 1，一旦少于 1 点血，骑士就会死去。

• 这一题首先想到的解题思路是动态规划。从终点逆推回起点。dp[i][j] 代表骑士进入坐标为 (i,j) 的格子之前最少的血量值。 那么 dp[m-1][n-1] 应该同时满足两个条件，dp[m-1][n-1] + dungeon[m-1][n-1] ≥ 1 并且 dp[m-1][n-1] ≥ 1，由于这两个不等式的方向是相同的，取交集以后，起决定作用的是数轴最右边的数，即 max(1-dungeon[m-1][n-1] , 1)。算出 dp[m-1][n-1] 以后，接着可以推出 dp[m-1][i] 这一行和 dp[i][n-1] 这一列的值。因为骑士只能往右走和往下走。往回推，即只能往上走和往左走。到这里，DP 的初始条件都准备好了。那么状态转移方程是什么呢？分析一般的情况，dp[i][j] 这个值应该是和 dp[i+1][j]dp[i][j+1] 这两者有关系。即 dp[i][j] 经过自己本格子的扣血以后，要能至少满足下一行和右一列格子血量的最少要求。并且自己的血量也应该 ≥1。即需要满足下面这两组不等式。

$\begin{matrix} \left\{ \begin{array}{lr} dp[i][j] + dungeon[i][j] \geqslant dp[i+1][j] \\ dp[i][j] \geqslant 1 \end{array} \right. \end{matrix}$

$\begin{matrix} \left\{ \begin{array}{lr} dp[i][j] + dungeon[i][j] \geqslant dp[i][j+1] \\ dp[i][j] \geqslant 1 \end{array} \right. \end{matrix}$
上面不等式中第一组不等式是满足下一行格子的最低血量要求，第二组不等式是满足右一列格子的最低血量要求。第一个式子化简即 dp[i][j] = max(1, dp[i+1][j]-dungeon[i][j])，第二个式子化简即 dp[i][j] = max(1, dp[i][j+1]-dungeon[i][j])。求得了这两种走法的最低血量值，从这两个值里面取最小，即是当前格子所需的最低血量，所以状态转移方程为 dp[i][j] = min(max(1, dp[i][j+1]-dungeon[i][j]), max(1, dp[i+1][j]-dungeon[i][j]))。DP 完成以后，dp[0][0] 中记录的就是骑士初始最低血量值。时间复杂度 O(m*n)，空间复杂度 O(m*n)。

• 这一题还可以用二分搜索来求解。骑士的血量取值范围一定是在 [1，+∞) 这个区间内。那么二分这个区间，每次二分的中间值，再用 dp 在地图中去判断是否能到达终点，如果能，就缩小搜索空间至 [1，mid]，否则搜索空间为 [mid + 1，+∞) 。时间复杂度 O(m*n* log math.MaxInt64)，空间复杂度 O(m*n)。

## 代码 #


package leetcode

import "math"

// 解法一 动态规划
func calculateMinimumHP(dungeon [][]int) int {
if len(dungeon) == 0 {
return 0
}
m, n := len(dungeon), len(dungeon[0])
dp := make([][]int, m)
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
}
dp[m-1][n-1] = max(1-dungeon[m-1][n-1], 1)
for i := n - 2; i >= 0; i-- {
dp[m-1][i] = max(1, dp[m-1][i+1]-dungeon[m-1][i])
}
for i := m - 2; i >= 0; i-- {
dp[i][n-1] = max(1, dp[i+1][n-1]-dungeon[i][n-1])
}
for i := m - 2; i >= 0; i-- {
for j := n - 2; j >= 0; j-- {
dp[i][j] = min(max(1, dp[i][j+1]-dungeon[i][j]), max(1, dp[i+1][j]-dungeon[i][j]))
}
}
return dp[0][0]
}

// 解法二 二分搜索
func calculateMinimumHP1(dungeon [][]int) int {
low, high := 1, math.MaxInt64
for low < high {
mid := low + (high-low)>>1
if canCross(dungeon, mid) {
high = mid
} else {
low = mid + 1
}
}
return low
}

func canCross(dungeon [][]int, start int) bool {
m, n := len(dungeon), len(dungeon[0])
dp := make([][]int, m)
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
}
for i := 0; i < len(dp); i++ {
for j := 0; j < len(dp[i]); j++ {
if i == 0 && j == 0 {
dp[i][j] = start + dungeon[0][0]
} else {
a, b := math.MinInt64, math.MinInt64
if i > 0 && dp[i-1][j] > 0 {
a = dp[i-1][j] + dungeon[i][j]
}
if j > 0 && dp[i][j-1] > 0 {
b = dp[i][j-1] + dungeon[i][j]
}
dp[i][j] = max(a, b)
}
}
}
return dp[m-1][n-1] > 0
}



Apr 8, 2023