题目
https://leetcode.com/problems/dungeon-game/
基本思路
动态规划（基本上难题都是动态规划问题，一定要好好掌握啊～） 从下向上计算（正着去救公主，我们就倒着求解） 还有一点要注意是，骑士无论到那个位置，必须健康值为1。 动态规划转换方程如下：
dp
[i
][j
] = min(dp
[i
+1][j
] - dungeon
[i
][j
], dp
[i
][j
+1] - dungeon
[i
][j
])
dp
[i
][j
] = max(dp
[i
][j
], 1)
实现代码
class Solution(object):
def calculateMinimumHP(self
, dungeon
):
"""
:type dungeon: List[List[int]]
:rtype: int
"""
row
,col
= len(dungeon
),len(dungeon
[0])
dp
= [[0]*col
for _
in range(row
)]
dp
[-1][-1] = max(1,1-dungeon
[-1][-1])
for i
in range(row
-2,-1,-1):
dp
[i
][col
-1] = max(1,dp
[i
+1][col
-1]-dungeon
[i
][col
-1])
for j
in range(col
-2,-1,-1):
dp
[row
-1][j
] = max(1,dp
[row
-1][j
+1]-dungeon
[row
-1][j
])
for i
in range(row
-2,-1,-1):
for j
in range(col
-2,-1,-1):
dp
[i
][j
] = max(1,min(dp
[i
+1][j
]-dungeon
[i
][j
],dp
[i
][j
+1]-dungeon
[i
][j
]))
return dp
[0][0]
