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.
| -2 (K) | -3 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
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.
leetcode 174这题值得注意。16年曾刷过，当时理解不透彻，现在重新刷仍然存在这个问题。另这题leetcode discuss和其他博客等都没有非常清楚的定义好状态。
这题比较确定的是到达公主房间后，骑士的血量为1就可以。如果正向推导很困难，且我们本身求的就是从骑士开始的血量。所以：
1.定义子状态dp[i][j]为：从(i, j)点到最右下角点公主房间所需要的最少初始血量。
2.返回的状态为dp[0][0]即从(0,0)到右下角点公主房间的最少初始血量。
3.转换状态，从右下开始朝左上走。即由dp[i][j+1], dp[i+1][j]推导得到dp[i][j]。 dp[i][j] + dungeon[i][j] = min(dp[i+1][j], dp[i][j+1])，即:dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]), 这样刚好维持继续朝右下走。同时需要注意题目提示If at any point his health point drops to 0 or below, he dies immediately。即任何时候血量都不能小于1，所以我们再做强制限制dp[i][j] >= 1。结合二者得到最终的状态dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])。
4.初始化，这题坐标型的题目如果状态方程多出一行或者一列会比较好处理，我们在左下各padding一行，一列。整个数组初始化为系统最大值。但是为了方便本身第m行，m列的处理。我们设置dp[m][n-1]为1， dp[m-1][n]为1。即方便dp[m-1][n-1]的初始化处理。即
| max | max | max | max |
| max | max | max | max |
| max | max | max | 1 |
| max | max | 1 | max |
代码如下：
class Solution(object): def calculateMinimumHP(self, dungeon): """ :type dungeon: List[List[int]] :rtype: int """ m = len(dungeon) n = len(dungeon[0]) minhealth = [[sys.maxint] * (n+1) for i in xrange(m+1)] minhealth[m][n-1] = 1 #注意 minhealth[m-1][n] = 1 #注意 for i in xrange(m-1, -1, -1): for j in xrange(n-1, -1, -1): minhealth[i][j] = max(1, min(minhealth[i][j+1], minhealth[i+1][j]) -dungeon[i][j]) return minhealth[0][0]
时间复杂度O(mn),空间复杂度为O(mn)可优化为O(m) 滚动数组。