题目大意：骑士在左上角(0, 0),公主在右下角(m, n)。骑士每次只能向右或者向下，每个方格表示骑士消耗获得的hp，题目要求骑士出发时候所需要的最小hp。在任何位置骑士的hp都要大于0
解题思路：假设dungeon的shape为(m, n)，我们建立一个shape为(m+1, n+1)的矩阵，index从0开始，最终要在(m-1, n-1)的位置有1个hp。那么按照题目的逻辑，从(m-1, n-1)能继续下去，在(m, n-1)和(m-1,n)都要至少要为1. 然后一步步朝左上角返回上去。
动态规划
class Solution(object):
def calculateMinimumHP(self, dungeon):
m = len(dungeon)
n = len(dungeon[0])
hp = [[float('inf') for _ in range(n + 1)] for _ in range(m + 1)]
hp[m][n - 1] = hp[m - 1][n] = 1
for y in range(m-1, -1, -1):
for x in range(n-1, -1, -1):
hp[y][x] = max(1, min(hp[y + 1][x], hp[y][x + 1]) - dungeon[y][x])
return hp[0][0]
if __name__ == "__main__":
Solution().calculateMinimumHP([[100]])