KK's blog

每天积累多一些

0%

LeetCode 174 Dungeon Game

Posted on Edited on Disqus:

LeetCode



The demons had captured the princess 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 was initially positioned in the top-left room and must fight his way through 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 (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight’s health (represented by positive integers).

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

Return the knight’s minimum initial health so that he can rescue the princess.

Note that 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.

Example 1:



Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.


Example 2:

Input: dungeon = [[0]]
Output: 1


Constraints:

m == dungeon.length n == dungeon[i].length
1 <= m, n <= 200 -1000 <= dungeon[i][j] <= 1000

题目大意：

保持正数健康值从左上走到右下

DP解题思路(推荐)：

坐标型DP。
dp[n][m]为通过这一格前的最小健康值，也就是题目所求，这意味着需要保证通过最后一个后的健康值为1，所以引入它相邻的两个cell为1
递归式为：

1
2
dp[n][m] = -dungeon[n][m] + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] < 0
         = max{1, min(dp[n+1][m], dp[n][m+1]) - dungeon[n][m]} if dungeon[n][m] > 0

由于-dungeon[n][m] + min(dp[n+1][m]一定为正数，所以可以归并两种情况：

1
dp[n][m] = max{1, min(dp[n+1][m], dp[n][m+1]) - dungeon[n][m]}

解题步骤：

N/A

注意事项：

  1. 从右下走回左上倒推初始值。每一格的最小健康值在为1，而初始健康值也最小为1.
  2. 递归式：一开始的递归式跟下和右格的极小值有关，所以DP数组(比原数组多出的)最右和最下边界初始值为正无穷；但根据公式，右下格会出现正无穷，所以需要特别处理，将右下格的相邻下右两格初始为1，可以这样理解，从右下格走出健康值必须是1
  3. 递归式：一开始写若该格dungeon值为负数，1 - dungeon[n][m] + min(dp[n+1][m], dp[n][m+1])这个1的确保证了最小健康值为1，但其实它只要加一次，而上述右下边界已经处理，所以递归式不需要+1，如[[-2, -3]], dp[0][1]=4, 而dp[0][0]为6即可
  4. 递归式：当dungeon为正数时，可以抵消它相邻格所要求的最低健康值，当然要保证健康值大于1，如[5, 4, -2], dp[0][0] = 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# dp[n][m] = 1 - dungeon[n][m] + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] < 0
#          = 1 + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] > 0
# dp[n][m] = -dungeon[n][m] + min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] < 0
#          = min(dp[n+1][m], dp[n][m+1]) if dungeon[n][m] > 0
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
	dp = [[float('inf') for _ in range(len(dungeon[0]) + 1)] for _ in range(len(dungeon) + 1)]
	dp[-1][-2] = dp[-2][-1] = 1
	for i in reversed(range(len(dungeon))):
		for j in reversed(range(len(dungeon[0]))):
			'''
			min_neighbor = float('inf')
			if i + 1 < len(dungeon):
				min_neighbor = min(min_neighbor, dp[i + 1][j])
			if j + 1 < len(dungeon[0]):
				min_neighbor = min(min_neighbor, dp[i][j + 1])
			if min_neighbor == float('inf'):
				min_neighbor = 0

			if dungeon[i][j] < 0:
				dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
			else:
				dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
			'''
			dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
	return dp[0][0]

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2)

Binary select算法II解题思路：

Binary select + DP
暴力法，假设某个初始健康值，然后用从左到右从上到下计算这一格后的健康值，dp[m][n] = max{dp[m-1][n], dp[m][n-1]} + dungeon[r][c], 可以看出dp定义和递归式max都是跟上述方法相反。求最后一个是否正数
暴力法是O(n^2), 而用binary select试0, 1000 * (m + n) + 1，1000是cell的最大值，m+n是路径长度，1是最小健康值，二分法试每个数值

参考https://leetcode.com/problems/dungeon-game/discuss/1498367

算法分析：

时间复杂度为O(n2)logn，空间复杂度O(n2)

Free mock interview