本文主要是介绍leetcode 174. Dungeon Game (地牢游戏),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意大致如下:
有个地牢,公主(P)被关在右下角格子里,骑士(K)会从左上角格子进入营救公主,骑士初始有一个血量。每个格子中可能有怪兽,会减掉骑士的血量(负数),也可能有药水,会增加骑士的血量(正数)。骑士的血量一旦减到0或者0以下,就会挂掉。问骑士能顺利营救公主所需要的初始血量。骑士每次只会向右边或者下面移动
需要注意的是在左上角的格子和右下角的格子,也就是骑士刚进入的格子和公主所在的格子也可能会减少血量。
思路:
从公主所在的格子倒推回初始的格子,
因为骑士每次只会向右边或者下边移动,所以只需要取右边和下边的较小值即可。
右边界的情况只需要看下边的格子,下边界只需要看右边的格子。
但是需要注意几点:
- 骑士的血量一旦到达0或者0以下会挂掉,所以要保证每个格子的血量至少是1.
- 营救到公主的最后一刻,即到达右下角的时候也要保证活着见到公主,所以初始化最后一格血量的时候要保证至少是1
- 需要的血量也就是至少是1的血量 减去 地牢中的数字
public int calculateMinimumHP(int[][] dungeon) {if(dungeon == null || dungeon.length == 0) {return 0;}int m = dungeon.length;int n = dungeon[0].length;int[][] dp = new int[m][n];//营救到公主的最后一刻也要保证血量至少是1dp[m-1][n-1] = Math.max(-dungeon[m-1][n-1] + 1, 1);//初始化右边界for(int i = m-2; i >= 0; i--) {dp[i][n-1] = Math.max(dp[i+1][n-1] - dungeon[i][n-1], 1);}//初始化下边界for(int j = n-2; j >= 0; j--) {dp[m-1][j] = Math.max(dp[m-1][j+1] - dungeon[m-1][j], 1);}for(int i = m-2; i >= 0; i--) {for(int j = n-2; j >= 0; j--) {//思路是取右边和下边的较小值,同时保证至少是1//但是为了减少计算量,取了简化版本//int right = Math.max(dp[i][j+1] - dungeon[i][j], 1);//int down = Math.max(dp[i+1][j] - dungeon[i][j], 1);//dp[i][j] = Math.min(right, down);dp[i][j] = Math.min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j];dp[i][j] = Math.max(dp[i][j], 1);}}return dp[0][0];}
这篇关于leetcode 174. Dungeon Game (地牢游戏)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!