# My AC Java Version, Suggestions are welcome

• ``````public int calculateMinimumHP(int[][] dungeon) {
if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) return 0;

int m = dungeon.length;
int n = dungeon[0].length;

int[][] health = new int[m][n];

health[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);

for (int i = m - 2; i >= 0; i--) {
health[i][n - 1] = Math.max(health[i + 1][n - 1] - dungeon[i][n - 1], 1);
}

for (int j = n - 2; j >= 0; j--) {
health[m - 1][j] = Math.max(health[m - 1][j + 1] - dungeon[m - 1][j], 1);
}

for (int i = m - 2; i >= 0; i--) {
for (int j = n - 2; j >= 0; j--) {
int down = Math.max(health[i + 1][j] - dungeon[i][j], 1);
int right = Math.max(health[i][j + 1] - dungeon[i][j], 1);
health[i][j] = Math.min(right, down);
}
}

return health[0][0];
}``````

• Although it's straightforward, but it would still be better to add some explanation and comment on the code IMHO.

• Thanks for the good solution.

As an improvement, it can also be solved without extra space.

Find below my accepted code. :

``````public int calculateMinimumHP(int[][] dun) {
int m = dun.length;
int n = dun[0].length;
int i,j;

dun[m-1][n-1]=Math.max(1,1-dun[m-1][n-1]);

for(i=m-2;i>=0;i--) dun[i][n-1] = Math.max(1,dun[i+1][n-1]-dun[i][n-1]);
for(i=n-2;i>=0;i--) dun[m-1][i] = Math.max(1,dun[m-1][i+1]-dun[m-1][i]);

for(i=m-2;i>=0;i--)
for(j=n-2;j>=0;j--)
dun[i][j]=Math.min(Math.max(1,dun[i+1][j]-dun[i][j]),Math.max(1,dun[i][j+1]-dun[i][j]));

return dun[0][0];

}
``````

• Before modifying the original matrix, it might be a good idea to ask the interviewer whether it is ok in my opinion.

• For DP problem, I always come up with recursion + memoization approach.
Someone may feel DP is straight-forward, someone may think the other.
Anyway, here is a top down recursive solution:

``````public class Solution {

int[][] mem;

private int helper(int[][] dungeon, int i, int j) {
if(i>=dungeon.length || j>=dungeon[0].length)
return Integer.MAX_VALUE;
if(mem[i][j]>0)
return mem[i][j];
int health = Integer.MAX_VALUE;
health = Math.min(health, helper(dungeon, i+1, j));
health = Math.min(health, helper(dungeon, i, j+1));
health = health==Integer.MAX_VALUE ? 1 : health; // this only happens with i, j is P already
int ret = health>dungeon[i][j] ? (health-dungeon[i][j]) : 1;
mem[i][j] = ret;
return ret;
}

public int calculateMinimumHP(int[][] dungeon) {
if(dungeon.length==0)
return 0;
mem = new int[dungeon.length][dungeon[0].length];
return helper(dungeon, 0, 0);
}
}``````

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