出口有两个，分别是右下角位置的下边和右边。
辅助数组的元素代表要从当前位置走到出口至少需要携带的血量。
想象地牢里的妖怪或者补给是在离开房间后生效。
当前至少需要x的血量，
地牢里是妖怪(-5)，则 x - 5 = y1(下边格子的值); x - 5 = y2(右边格子的值)
取这两个方程的最小值，因为你可以选择走的方向，选择最少携带的血量。
如果地牢里是草药，两个方程计算出来的最小值有可能是负数，此时需要1的血量，代表在这个格子有1的血量，然后跳出来，加上草药的补给后，血量大于等于预期的(y1和y2中的最小值).
def calculateMinimumHP(self, dungeon):
"""
:type dungeon: List[List[int]]
:rtype: int
"""
if len(dungeon) == 0:
return 1
m = len(dungeon)
n = len(dungeon[0])
# 初始化辅助数组,比dungeon多一行和一列
# 边缘初始化为inf,避免从边缘走到目标点
# 目标点两个:原数组右下角的右边和下边,初始化为1
res = []
for i in range(m + 1):
temp = [float("inf")] * (n + 1)
res.append(temp)
res[m][n-1] = 1
res[m-1][n] = 1
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
# 通过往右或者往下走,到达右边或者下边之后,经过当前的消耗或者补给,还能满足右边或者下边的要求
# 取往右或者往下的最小值
# 如果最小值小于1,设置为1,因为从其他地方到达当前位置之后,至少还要有1的血量
hp = min(res[i+1][j] - dungeon[i][j], res[i][j+1] - dungeon[i][j])
if hp < 1:
hp = 1
res[i][j] = hp
return res[0][0]
