题目大意：从左上角到右下角，每一个格子都有各自的权值，如果权值为负，则当到达时，要失血；如果权值为正，则当到达时，要加血。当到达某个格子时，当前血量<=0，则死亡，到达不了右下角，所以此时要计算从左上角到右下角，初始应该最少携带多少血（即经过所有路径后所计算出的值），才不会死亡，能正常到达右下角。
法一：dfs，模板深搜，果断超时。要注意：更新点不是整条路径的和（与64题比较）的最小值，而是整条路径中所达到的最大的失血量，如果最大失血量>=0，则本身只需要携带1个血即可；否则本身携带的血应该=abs(最大失血量)+1。代码如下：
public int calculatedMinimumHP(int[][] dungeon) {
boolean vis[][] = new boolean[dungeon.length][dungeon[0].length];
int f[][] = {{1, 0}, {0, 1}};
vis[0][0] = false;
return dfs(dungeon, 0, 0, dungeon[0][0], Integer.MAX_VALUE, dungeon[0][0], vis, f);
}
public int dfs(int[][] dungeon, int x, int y, int sum, int res, int blood, boolean vis[][], int f[][]) {
if(x == dungeon.length - 1 && y == dungeon[0].length - 1) {
//递归结束点是每条线路的过程中的最大失血量
if(blood < 0) {//如果失血量为负数，则是绝对值+1
if(Math.abs(blood) < res) {
res = Math.abs(blood) + 1;
}
}
else {//如果失血量>=0，则是1，因为当失血量为0时，也会死亡
res = 1;
}
return res;
}
for(int i = 0; i < 2; i++) {
int cnt_x = x + f[i][0];
int cnt_y = y + f[i][1];
if(cnt_x < dungeon.length && cnt_y < dungeon[0].length && vis[cnt_x][cnt_y] == false) {
vis[cnt_x][cnt_y] = true;
res = dfs(dungeon, cnt_x, cnt_y, sum + dungeon[cnt_x][cnt_y], res, blood < (sum + dungeon[cnt_x][cnt_y]) ? blood : (sum + dungeon[cnt_x][cnt_y]), vis, f);
vis[cnt_x][cnt_y] = false;
}
}
return res;
}
法二（借鉴）：dp，类似于64的二维dp，64是从左上往右下，而这题是从右下往左上。dp[i][j]表示从坐标[i,j]到右下角的路径中需要的最少血量，这样每次计算时，都可以用到下面和右面的dp值，从中取最小再将当前值减去即可。其中要追的地方与dfs相似，在每一个格子中，都要始终保持至少1个血量。dp公式：dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - du[i][j]。代码如下（耗时2ms）：
public int calculatedMinimumHP(int[][] dungeon) {
int dp[][] = new int[dungeon.length][dungeon[0].length];
//初始化最后一列
//由于走到每个格子时，都要保持至少一个血量，所以应该用到max(1, ...)
dp[dungeon.length - 1][dungeon[0].length - 1] = Math.max(1, 1 - dungeon[dungeon.length - 1][dungeon[0].length - 1]);
for(int i = dungeon.length - 2; i >= 0; i--) {
dp[i][dungeon[0].length - 1] = Math.max(1, dp[i + 1][dungeon[0].length - 1] - dungeon[i][dungeon[0].length - 1]);
}
//初始化最后一行
for(int i = dungeon[0].length - 2; i >= 0; i--) {
dp[dungeon.length - 1][i] = Math.max(1, dp[dungeon.length - 1][i + 1] - dungeon[dungeon.length - 1][i]);
}
//计算dp
for(int i = dungeon.length - 2; i >= 0; i--) {
for(int j = dungeon[0].length - 2; j >= 0; j--) {
//从下边和右边中取出最小者，然后减去当前值
dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
}
}
return dp[0][0];
}