网站建设属于哪个经营范围,怎么做网站可以注册的,网站策划书中应包括市场竞争对手的信息,网站内容维护更新方法一些恶魔抓住了公主#xff08;P#xff09;并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士#xff08;K#xff09;最初被安置在左上角的房间里#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正…一些恶魔抓住了公主P并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士K最初被安置在左上角的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快到达公主骑士决定每次只向右或向下移动一步。 编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如考虑到如下布局的地下城如果骑士遵循最佳路径 右 - 右 - 下 - 下则骑士的初始健康点数至少为 7。
-2 (K) -3 3 -5 -10 1 10 30 -5 (P)
说明:
骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。 这题想了两天最后也没搞出来看了大佬的思路才会的。。。。
这道题意思就是从左上角如何到右下角只能向右向下在这之间有加血有扣血如何初始血量使得正好到达。
其实我们可以倒过来想。从右下角保持多少血量能到达左上角。
我们用 dp[i][j]表示在i,j位置最少需要的血量
动态方程dp[i][j] max(1, min(dp[i1][j], dp[i][j1]) - dungeon[i][j])
最后一行和最后一列做特殊处理
题中给的案例是
-2 -3 3
-5 -10 1
10 30 -5
那么从最后一点开始推测最后一点需要6点血才可以
那么他上面那一行的1处因为可以加一点血所以到那有五点血就可以
最后推导出来各点的血量就是
7 5 2
6 11 5
1 1 6
提交的代码
class Solution { public int calculateMinimumHP(int[][] dungeon) { int m dungeon.length; int n dungeon[0].length; int[][] dp new int[m][n]; int i,j; if(dungeon[m-1][n-1]0) { dp[m-1][n-1]1java.lang.Math.abs(dungeon[m-1][n-1]); } else { dp[m-1][n-1]1; } for(im-1;i0;i--) { for(jn-1;j0;j--) { if(im-1j!n-1) { dp[i][j] java.lang.Math.max(1,dp[i][j1]-dungeon[i][j]); } else if(i!m-1jn-1) { dp[i][j] java.lang.Math.max(1,dp[i1][j]-dungeon[i][j]); } else if(i!m-1j!n-1) { dp[i][j] java.lang.Math.max(1,java.lang.Math.min(dp[i1][j],dp[i][j1])-dungeon[i][j]); } } } return dp[0][0]; } }
完整的代码 public class Solution174 { public static int calculateMinimumHP(int[][] dungeon) { int m dungeon.length; int n dungeon[0].length; int[][] dp new int[m][n]; int i,j; if(dungeon[m-1][n-1]0) { dp[m-1][n-1]1java.lang.Math.abs(dungeon[m-1][n-1]); } else { dp[m-1][n-1]1; } for(im-1;i0;i--) { for(jn-1;j0;j--) { if(im-1j!n-1) { dp[i][j] java.lang.Math.max(1,dp[i][j1]-dungeon[i][j]); } else if(i!m-1jn-1) { dp[i][j] java.lang.Math.max(1,dp[i1][j]-dungeon[i][j]); } else if(i!m-1j!n-1) { dp[i][j] java.lang.Math.max(1,java.lang.Math.min(dp[i1][j],dp[i][j1])-dungeon[i][j]); } } } return dp[0][0]; } public static void main(String[] args) { int[][] nums {{-2,-3,3},{-5,-10,1},{10,30,-5}}; //int[][] nums {{0,0,0},{1,1,-1}}; //int[][] nums {{-200}}; System.out.println(calculateMinimumHP(nums)); } }
