# 1. 只能两个方向 -> 动态规划；2. 中途必须大于1 -> 从目标出发
# 空间复杂度可进一步优化至O(n)
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
m = len(dungeon)
n = len(dungeon[0])
dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
dp[m][n-1] = 1
dp[m-1][n] = 1
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
return dp[0][0]