# clean 3ms Java DP solution

• The idea is to start build from the destination. hp[i][j] means the minimal hp needed to move from cell [i,j] to destination.

Since we can also build the matrix line by line, the space complexity can be reduced to the length of each line and we use hp[j] in line i to stand for the cell hp[i][j]

Whenever the "minimal hp needed to reach the destination" become negtive or zero, reset the cell to 1, which means when reach this cell, the minimal hp should be 1.

``````public int calculateMinimumHP(int[][] dungeon) {
int M = dungeon.length;
int N = dungeon[0].length;
int[] hp = new int[N];

hp[N-1] = (dungeon[M-1][N-1] <= 0) ? 1-dungeon[M-1][N-1] : 1;
for(int j = N-2; j >= 0; --j){
hp[j] = (hp[j+1] - dungeon[M-1][j] <= 0) ? 1 : hp[j+1] - dungeon[M-1][j];
}

for(int i = M-2; i >= 0; --i){
hp[N-1] = (hp[N-1] - dungeon[i][N-1] <= 0) ? 1 : hp[N-1] - dungeon[i][N-1];
for(int j = N-2; j >= 0; --j){
int hpfromr = (hp[j+1] - dungeon[i][j] <= 0) ? 1 : hp[j+1] - dungeon[i][j];
int hpfromd = (hp[j] - dungeon[i][j] <= 0) ? 1 : hp[j] - dungeon[i][j];
hp[j] = (hpfromr > hpfromd) ? hpfromd : hpfromr;
}
}

return hp[0];
}``````

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