被墙网站查询,flash互动网站开发,买了一个域名怎么做网站,一流校建设网站地下城游戏
题目链接#xff1a;174. 地下城游戏
状态表示#xff1a; 按照以往题的表示#xff0c;dp[i][j]表示#xff1a;从起点#xff08;0#xff0c;0#xff09;位置到达#xff08;i#xff0c;j#xff09;位置时#xff0c;所需的最小初始健康值。但是…地下城游戏
题目链接174. 地下城游戏
状态表示 按照以往题的表示dp[i][j]表示从起点00位置到达ij位置时所需的最小初始健康值。但是如果这么去表示不仅要考虑到达ij位置的最小初始健康值由于魔法球的存在还需要考虑到达ij位置时的健康值因为魔法球会对算后续位置的最小初始健康值产生影响
下面用题目中的示例1为例演示: 由此可知到达魔法球位置所需的最低初始健康值和上一次的最低初始健康值保持一致而魔法球会增加健康值这就会对后面的结果产生影响因此我们不仅要考虑到达ij位置的最小初始健康值还需要考虑到达ij位置时的健康值以保证后续结果的正确性
因此我们可以试着用dp[i][j]表示以ij位置为起点到达终点位置时所需的最小健康值。当(i,j)位置是魔法球时可以用之前的dp[i1][j]和dp[i][j1]中的最小健康值减去治疗量就能得到当前的位置到达终点位置时所需的最小健康值dp[i][j]注意dp[i][j]不能小于0最小值为1)当(i,j)位置是恶魔时也是这样处理实际上就是加上了需要扣除的健康值 通过这种状态表示我们最终能够求得结果
总结
这道题的难点在于怎么去处理健康值增加的问题健康值的增加不能为之前的损失提供帮助只会对后续有帮助如果按照第一种状态表示dp[i][j]仅仅只表示了从00位置到达ij位置所需的最小初始健康值而由于魔法球的存在导致后续的健康值会增加因此我们还需要去记录当前位置的健康值以保证后续计算最小初始健康值的正确性如果按照第二种状态表示dp[i][j]表示从00位置出发按照最优路径到达ij位置时还需要剩余的最小健康值为了到达终点后健康值为1。即dp[i][j]不仅表示了从ij位置到达终点位置所需的最小初始健康值还表示了从00位置出发到达ij位置时所需剩余的最小健康值即当前健康值比较两种状态表示可知第二种表示更合理更方便后续的填表
状态转移方程 dp[i][j] min(dp[i1][j],dp[i][j1])-d[i][j]dp[i][j] max(1, dp[i][j])
初始化 创建表时多创建一行(第m行)和一列第n列除dp[m][n-1] 1dp[m-1][n] 也可初始化为1表示救出公主后还需剩余1点健康值其他都初始化为正无穷(以防对填表产生影响)
填表顺序 从下往上每一行从右往左
返回值 dp[0][0]
实现代码
class Solution {public int calculateMinimumHP(int[][] dungeon) {//1.创建dp表int m dungeon.length;int n dungeon[0].length;int[][] dp new int[m1][n1];//2.初始化for(int row 0; row m1; row) {dp[row][n] Integer.MAX_VALUE;}for(int col 0; col n1; col) {dp[m][col] Integer.MAX_VALUE;}dp[m][n-1] 1;//3.填表for(int i m-1; i 0; i--) {for(int j n-1; j 0; j--) {dp[i][j] Math.min(dp[i1][j], dp[i][j1]) - dungeon[i][j];dp[i][j] Math.max(1, dp[i][j]);}}//4.返回值return dp[0][0];}
}
