BiruLyu
6/16/2017 - 1:18 AM

## 174. Dungeon Game(#1).java

``````public class Solution {
private int result = Integer.MAX_VALUE;
private int[][] dirs = {{1,0}, {0,1}};
public int calculateMinimumHP(int[][] dungeon) {
int[][] cache = new int[dungeon.length][dungeon[0].length];
int res = dfs(dungeon, 0, 0, cache);
return res > 0 ? 1 : ((-1)*res+1);

}

private int dfs(int[][] dungeon, int x, int y, int[][] cache) {
if(x == dungeon.length-1 && y == dungeon[0].length-1) {
return dungeon[x][y] > 0 ? 0 : dungeon[x][y];
}

if(cache[x][y] != 0) {
return cache[x][y] == -1 ? 0 : cache[x][y];
}

int result = Integer.MIN_VALUE;
for(int[] dir : dirs) {
int x0 = x + dir[0];
int y0 = y + dir[1];

if(x0 >= dungeon.length || y0 >= dungeon[0].length) {
continue;
}
result = Math.max(result, dfs(dungeon, x0, y0, cache));
}

cache[x][y] = (result+dungeon[x][y]) > 0 ? -1 : (result+dungeon[x][y]);
return (result+dungeon[x][y]) > 0 ? 0 : (result+dungeon[x][y]);
}
}``````
``````public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int res = Integer.MAX_VALUE;
if (dungeon == null || dungeon.length < 1 || dungeon[0].length < 1) return res;
int row = dungeon.length;
int col = dungeon[0].length;
int[][] dp = new int[row + 1][col + 1];
for (int i = 0; i <= row; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}

dp[row][col - 1] = 1;
dp[row - 1][col] = 1;
//dp[row - 1][col - 1] = 0;
for (int i = row - 1; i >= 0; i--) {
for (int j = col - 1; j >= 0; j--) {
if (dungeon[i][j] >= dp[i + 1][j] || dungeon[i][j] >= dp[i][j + 1]) {
dp[i][j] = 1;
} else {
dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
}
}
}
return dp[0][0];
}
}``````