【重点】【DP】174.地下城游戏

题目

DP

参考解答：https://blog.csdn.net/weixin_70056514/article/details/131513364
重要步骤：


两个关键点：
（1）骑士的健康点数必须始终为正整数，若 ≤ 0会原地死亡；
（2）骑士到达最后一格后，健康点数必须 ≥ 1，到达最有1格后，保底不死；

Python

class Solution:def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:m, n = len(dungeon), len(dungeon[0])dp = [[0]*(n+1) for _ in range(m+1)]for i in range(m+1):for j in range(n+1):if i == m or j == n:dp[i][j] = infdp[m][n-1], dp[m-1][n] = 1, 1for i in range(m-1, -1, -1):for j in range(n-1, -1, -1):dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]dp[i][j] = max(dp[i][j], 1)return dp[0][0]