# My Java AC solution with DP and O(1) space

• Start from the destination, we can calculate the minimum HP required then store it in the cell since we won't be needing it later. This way we can achieve constant space.

If we care not allowed to change the matrix, then we need at least a 1-D array.

``````public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
// return 0 if dungeon does not exist
if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) return 0;
int m = dungeon.length -1, n = dungeon[0].length -1;
//make sure alive after rescue
dungeon[m][n] = setHp(1-dungeon[m][n]);

//fill bottom row and right-most column
for (int i = m-1; i >= 0; i--)
dungeon[i][n] = setHp(dungeon[i+1][n] - dungeon[i][n]);
for (int j = n-1; j >= 0; j--)
dungeon[m][j] = setHp(dungeon[m][j+1] - dungeon[m][j]);

//fill the rest
for (int i = m-1; i >= 0; i--)
for (int j = n-1; j >= 0; j--)
//pick minimum hp needed after this cell
dungeon[i][j] = setHp(Math.min(dungeon[i+1][j],dungeon[i][j+1])-dungeon[i][j]);

return dungeon[0][0];
}
//if needed Hp is negative set hp to 1, otherwise positive
private int setHp (int hp) {
return hp <= 0 ? 1: hp;
}
}``````

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