题目：

  1. 一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。
  2. 我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
  4. 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
  6. 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数
  7. （若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），
  8. 要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
  10. 为了尽快到达公主，骑士决定每次只向右或向下移动一步。
  12. 编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
  14. 例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，
  15. 则骑士的初始健康点数至少为 7。
  17. -2 (K)    -3    3
  18. -5    -10    1
  19. 10    30    -5 (P)
  21. 说明:
  23. 骑士的健康点数没有上限。
  25. 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，
  26. 包括骑士进入的左上角房间以及公主被监禁的右下角房间。
  28. 来源：力扣（LeetCode）
  29. 链接：https://leetcode-cn.com/problems/dungeon-game
  30. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

30min，dp方向反了

  1. class Solution:
  2.     def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
  3.         if not dungeon or not dungeon[0]:return 0
  4.         m,n=len(dungeon),len(dungeon[0])
  5.         dp=[[0]*n for _ in range(m)]
  7.         for i in range(m-1,-1,-1):
  8.             for j in range(n-1,-1,-1):
  9.                 if i==m-1 and j==n-1:dp[i][j]= max(1,1-dungeon[i][j])
  10.                 elif i==m-1:
  11.                     dp[i][j]= max(1,dp[i][j+1]-dungeon[i][j])
  12.                 elif j==n-1:
  13.                     dp[i][j]= max(1,dp[i+1][j]-dungeon[i][j])
  14.                 else:
  15.                     temp=min(dp[i][j+1],dp[i+1][j])
  16.                     dp[i][j]= max(1,temp-dungeon[i][j])
  17.         return dp[0][0]

要点：

1. dp 定义

从终点往起点倒着dp是对的，因为这样符合dp的无后效性。
如果从起点往终点dp，当前血量和最大扣血都是要考虑 的因素，而且随着后面的格子，侧重点不一样，所以不满足dp的无后效性。

2. 边界

可以多开1列1行，令他们角上为1，其余为大数，但是也不一定好用，容易混下标。但是这题还是很好的处理。

其他：

代码报错：无，就是太菜了啊