# Java DP solution with explain

• My idea is I create array dp[][] to store the min health needed if K start from that room dp[i][j], and I calculate from the last room which is dp[m-1][n-1]. The [m-1][n-1] should equal 0 if the dungeon[m-1][n-1] larger than 0, or it equals dungeon[m-1][n-1], if dungeon[m-1][n-1] <0.

The base case is m-1 row and n-1 column. For m-1 row, it should equal 0 if its value + the right room's val >0, or it equals its value + the right room's val. It is same for the n-1 column.

For the other room, I calculate the max val between the right room and down room + itself. If the result larger than 0 I put 0 here, or the result.

Sorry for my poor English.

``````public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int m=dungeon.length;
int n=dungeon[0].length;
if(m==0||n==0){
return 0;
}
int[][] dp=new int[m][n];
dp[m-1][n-1]=dungeon[m-1][n-1]>0?0:dungeon[m-1][n-1];
for(int i=n-2;i>=0;i--){
int val=dp[m-1][i+1]+dungeon[m-1][i];
if(val>=0){
dp[m-1][i]=0;
}else{
dp[m-1][i]=val;
}
}
for(int i=m-2;i>=0;i--){
int val=dp[i+1][n-1]+dungeon[i][n-1];
if(val>=0){
dp[i][n-1]=0;
}else{
dp[i][n-1]=val;
}
}
for(int i=m-2;i>=0;i--){
for(int j=n-2;j>=0;j--){
int val=Math.max(dp[i+1][j],dp[i][j+1])+dungeon[i][j];
if(val>=0){
dp[i][j]=0;
}else{
dp[i][j]=val;
}
}
}
return -dp[0][0]+1;

}
}``````

• My simple and short solution:

public class Solution {
public int calculateMinimumHP(int[][] dungeon) {

``````    if(dungeon==null || dungeon.length==0)
return 0;
int x=dungeon.length-1;
int y=dungeon[0].length-1;
dungeon[x][y]=Math.max(1-dungeon[x][y], 1);

for(int i=y-1;i>=0;i--)
dungeon[x][i]=Math.max(dungeon[x][i+1]-dungeon[x][i], 1);

for(int i=x-1;i>=0;i--)
dungeon[i][y]=Math.max(dungeon[i+1][y]-dungeon[i][y], 1);

for(int i=x-1;i>=0;i--){
for(int j=y-1;j>=0;j--){
int right=Math.max(dungeon[i][j+1]-dungeon[i][j], 1);
int left=Math.max(dungeon[i+1][j]-dungeon[i][j], 1);
dungeon[i][j]=Math.min(left, right);
}
}
return dungeon[0][0];
}
``````

}

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