174.地牢游戏题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/dungeon-game题目一些恶魔抓住了公主（P），并将她锁在地牢的右下角。地牢是由MxN房间组成的二维网格。我们的英雄骑士（K）最初被安置在左上角的房间，他必须穿越地牢，与恶魔战斗拯救公主。骑士的初始生命值是一个正整数。如果他的生命值在某个时候下降到0或以下，他会立即死亡。有些房间有恶魔守卫，骑士进入这些房间会损失生命值（如果房间内的值为负整数，则表示骑士会损失生命值）；其他房间要么是空的（房间里的值为0），要么有增加骑士生命值的魔法球（如果房间里的值为正整数，则表示骑士会增加生命值）。为了尽快到达公主身边，骑士决定一次只向右或向下移动一步。编写一个函数来计算确保骑士能够拯救公主所需的最低初始健康点数。例如，考虑具有以下布局的地牢，如果骑士遵循最佳路径右->右->下->下，则骑士的初始生命值至少为7。-2(K)-33-5-1011030-5(P)说明：骑士的生命值没有上限。任何房间都可以威胁或增加骑士的生命值，包括骑士进入的左上房间和囚禁公主的右下房间。解题思路：动态规划先说一下需要注意的点：【题目中已经说明战士只能向右下移动】，【如果战士的生命值下降到0或以下时某一刻，他将立即死去】。在这个问题中，我们将使用逆向动态规划。如果选择使用正向动态规划，dp值的更新会比较困难。粗略的解释一下这种情况，假设有如下二维网格：现在假设右下角的目标端点有如下走法：这里，我们首先需要记录[路径总和]和[路由的最小初始化值]：先看上面红色路由：从左上角(0,0)到(1,2)，[路径总和]为2，[最小初始化值]为4;然后看绿色路线：从左上角(0,From0)到(2,1)，[PathSum]为1，[MinimumInitializationValue]为3。如前所述，需要做的点需要注意的是，战士的血量必须时刻大于0。那么，在我们的路线规划中，一定要保证【路径总和】尽可能大，【最小初始化值】尽可能小。Intheaboveexample,wewillfinallychoosetheredroute,becausewhentheredrouteisselected,ifthe[minimuminitializationvalue]is4,itispossibletoreachtheend.而如果选择绿色路线，如果要走到尽头，由于【路径总和】较小，此时需要将【最小初始化值】增加到5才能安全到达。但是，如果结束位置（即右下角坐标(2,2)）的值-5变为大于等于0的值，此时情况就会发生变化。当终点值发生变化时，红色路线【最小初始化值】仍然是4，但是绿色路线【最小初始化值】将只需要3。根据上面的分析，我们可以发现，如果选择前向动态规划，我们不能满足动态规划的[无后效]。那么此时我们考虑逆向动态规划。状态定义令dp[i][j]表示从(i,j)到达终点所需的最小初始化值。我们使用反向动态规划进行状态转移，所以这里dp[i][j]只需要关心dp[i][j+1]和dp[i+1][j]中的最小值，而当前点的值为dungeon[i][j]。这里，初始值必须大于等于1，则此时的状态转移方程为：dp[i][j]=max(min(dp[i][j+1],dp[i+1][j]-dungeon[i][j]),1)我们最终需要的是dp[0][0]。状态初始化首先考虑边界问题：当i=m-1且j=n-1时，dp[i][j+1]和dp[i+1][j]会出现越界问题，并将两个值都设为1。即：dp[m-1][n]=1,dp[m][n-1]=1具体代码实现如下。代码实现类解：defcalculateMinimumHP(self,dungeon:List[List[int]])->int:m=len(dungeon)n=len(dungeon[0])dp=[[float('inf')]*(n+1)for_inrange(m+1)]#初始化值dp[m-1][n]=1dp[m][n-1]=1foriinrange(m-1,-1,-1):对于范围(n-1,-1,-1)中的j:dp[i][j]=max(min(dp[i][j+1],dp[i+1][j])-dungeon[i][j],1)返回dp[0][0]得到结果，欢迎关注公众号【藏书】
