# DFS+Cache, beat 98.8%. Including transfer to DP & space optimize

• DFS+Cache:

``````public class Solution {
int[][] cache;
public int calculateMinimumHP(int[][] dungeon) {
cache = new int[dungeon.length][dungeon[0].length];
int ret = search(dungeon, 0, 0);
return ret > 0 ? 1 : -ret + 1;
}
private int search(int[][] matrix, int x, int y) {
if (x == matrix.length - 1 && y == matrix[0].length - 1) return matrix[x][y] > 0 ? 0 : matrix[x][y];
if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length) return Integer.MIN_VALUE;
if (cache[x][y] != 0) return cache[x][y] == -1 ? 0 : cache[x][y];

int left = search(matrix, x + 1, y);
int right = search(matrix, x, y + 1);
int cur = matrix[x][y] + Math.max(left, right);

cache[x][y] = cur > 0 ? -1 : cur;
return cur > 0 ? 0 : cur;
}
}
``````

DP:

``````public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int row = dungeon.length, col = dungeon[0].length;
int[][] F = new int[row][col];
for (int i = row - 1; i >= 0; i--) {
for (int j = col - 1; j >= 0; j--) {
if (i == row - 1 && j == col - 1) F[i][j] = dungeon[i][j] > 0 ? 0 : dungeon[i][j];
else {
int left = i + 1 >= row ? Integer.MIN_VALUE : F[i + 1][j];
int right = j + 1 >= col ? Integer.MIN_VALUE : F[i][j + 1];
int cur = dungeon[i][j] + Math.max(left, right);
F[i][j] = cur > 0 ? 0 : cur;
}
}
}
return F[0][0] > 0 ? 1 : -F[0][0] + 1;
}
}
``````

Space optimize to O(n):

``````public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int row = dungeon.length, col = dungeon[0].length;
int[][] F = new int[2][col];
for (int i = row - 1; i >= 0; i--) {
for (int j = col - 1; j >= 0; j--) {
if (i == row - 1 && j == col - 1) F[i % 2][j] = dungeon[i][j] > 0 ? 0 : dungeon[i][j];
else {
int left = i + 1 >= row ? Integer.MIN_VALUE : F[(i + 1) % 2][j];
int right = j + 1 >= col ? Integer.MIN_VALUE : F[i % 2][j + 1];
int cur = dungeon[i][j] + Math.max(left, right);
F[i % 2][j] = cur > 0 ? 0 : cur;
}
}
}
return F[0][0] > 0 ? 1 : -F[0][0] + 1;
}
}
``````

I also come up with a DP solution, which is more complicated than you. So I hope you can give more explanation about your idea. Thx.

• @biaoge could I know if you understand the DFS solution. My DP comes from the DFS. Would you want me to explain the DFS, or how to transfer the DFS to DP

• @lusoul hi, I wish you explain the DFS + Cache solution. If you could explain DFS solution, I think maybe I could transfer DFS to DP by myself. Thx

• @biaoge

比较需要注意的一点是，取left和right的最大值 + matrix[x][y]=cur, 如果cur是大于0的数，直接返回0即可，因为cur表示当前点最少需要的生命值，并不会影响到上一层，只有当cur<0时才会影响到上一层

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.