盐城做网站网络公司电话?,天津市建设厅建筑业信息网,app定制大概多少钱,乐清做网站培训文章目录1题目理解2 分析1题目理解
故事背景#xff1a;恶魔把公主抓走了#xff0c;关在地牢里面。骑士想要把公主救出来。初始化的时候#xff0c;骑士有一个健康值init。 输入#xff1a;int[][] dungeon表示地牢中魔鬼布局图。dungeon[i][j]0#xff0c;恶魔会提…
文章目录1题目理解2 分析1题目理解
故事背景恶魔把公主抓走了关在地牢里面。骑士想要把公主救出来。初始化的时候骑士有一个健康值init。 输入int[][] dungeon表示地牢中魔鬼布局图。dungeon[i][j]0恶魔会提高骑士的健康值dungeon[i][j]dungeon[i][j]会降低 骑士健康值掉血。如果骑士健康值为0那骑士就牺牲了。 输出骑士需要的最小健康值。 例如 输入
-2 (K)-33-5-1011030-5P
输出7 按照 右-右-下-下的路线健康值最小是7即可。
2 分析
解题思路来源于力扣。 从左上角走到右下角有很多种走法参考63题。找到每一种需要的最小健康值求最小值就是答案。对于这种比较难的题目会先列出解题框架然后再分析填充。 先写暴力搜索的框架。将与状态无关的变量dungeonmn等放到实例变量中。从(0,0)开始走横纵坐标是状态相关的作为方法参数。
class Solution {private int[][] dungeon;private int m;private int n;private int minHealth;public int calculateMinimumHP(int[][] dungeon) {this.dungeon dungeon;m dungeon.length;n dungeon[0].length;minHealth Integer.MAX_VALUE;visit(0,0);return minHealth;}private void visit(int i, int j){if(im || jn){....return;}...}
}需要保证骑士在到达(i,j)之后健康值大于0那就需要上一步的健康值。 从(i,j)可以达到(i1,j)、(i,j1)。
class Solution {...public int calculateMinimumHP(int[][] dungeon) {this.dungeon dungeon;m dungeon.length;n dungeon[0].length;minHealth Integer.MAX_VALUE;visit(0,0,0);return minHealth;}private void visit(int i, int j, int preHealth){if(im || jn){return;}int health preHealth dungeon[i][j];...}
}health如果小于1那么就需要abs(health)1的初始健康值。 health如果大于 1那么就初始健康值可以为0。 也就是 init0 if health1initabs(health)1,if health0 找到了当前状态的init还需要查找到这条路径上最大的init才是就出公主的当前路径上需要的最小的init。例如-2--3-3-1--5这条路径。在(0,1)这一点health6,那么init0。在(0,2),init 3。需要找到这条路径上的最大值才能保证走这条路完成任务。
class Solution {...private void visit(int i, int j, int preHealth,int maxInitOfPath){if(im || jn){return;}preHealth dungeon[i][j];int init preHealth1?0:Math.abs(preHealth)1;maxInit Math.max(maxInit,init);}
}接下来分析完成的标志是到达(m,n-1)或者m-1,n。达到(m-1,n-1)之后再走一步确定全局最小init。 public int calculateMinimumHP(int[][] dungeon) {this.dungeon dungeon;m dungeon.length;n dungeon[0].length;minHealth Integer.MAX_VALUE;visit(0,0,0,0);return minHealth;}private void visit(int i, int j, int preHealth,int maxInitOfPath){if(im-1 jn || im jn-1){minHealth Math.min(minHealth,maxInitOfPath);return;}if(im || jn){return;}preHealth dungeon[i][j];int init preHealth1?0:Math.abs(preHealth)1;maxInitOfPath Math.max(maxInitOfPath,init);visit(i1,j,preHealth,maxInitOfPath);visit(i,j1,preHealth,maxInitOfPath);}minHealth就是最小需要的初始健康值。 再进一步观察发现preHealth其实就是路径上dungeon[i][j]的和。maxInitOfPath的取值和整条路径中的的最小值有关系。也就是说路径和、路径上的最小值与最终结果有关系。动态规划只能表示一个变量没有办法把这两个因素都放入转移方程。
如果从右下角向左上角进行递归我们需要保证达到(i,j)的时候的路径和preSumdungeon[i][j]即可。 令dp[i][j] 表示从坐标 (i,j)(i,j) 到终点所需的最小初始值dp[i][j]与dp[i1][j]、dp[i][j1]有关系 。 dp[i][j]min(dp[i1][j],dp[i][j1])−dungeon[i][j]dp[i][j] min(dp[i1][j],dp[i][j1]) - dungeon[i][j]dp[i][j]min(dp[i1][j],dp[i][j1])−dungeon[i][j]。 考虑初始化dp[m-1][n] dp[m][n-1]1。
class Solution {public int calculateMinimumHP(int[][] dungeon) {int m dungeon.length;int n dungeon[0].length;int[][] dp new int[m1][n1];for(int[] d : dp){Arrays.fill(d,Integer.MAX_VALUE);}dp[m][n-1]dp[m-1][n]1;for(int im-1;i0;i--){for(int jn-1;j0;j--){int min Math.min(dp[i1][j], dp[i][j1]);dp[i][j] Math.max(min-dungeon[i][j],1);}}return dp[0][0];}}
