# JAVA short DP + explaination

• ``````public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int column = dungeon.length;
int row = dungeon[0].length;
int[][] dp = new int[column][row];
dp[column-1][row-1] = Math.max(1-dungeon[column-1][row-1], 1);

for(int i=column-2; i>=0; i--) {
dp[i][row-1] = Math.max(1, dp[i+1][row-1]-dungeon[i][row-1]);
}
for(int j=row-2; j>=0; j--) {
dp[column-1][j] = Math.max(1, dp[column-1][j+1]-dungeon[column-1][j]);
}
for(int i=column-2; i>=0; i--) {
for(int j=row-2; j>=0; j--) {
dp[i][j] = Math.max(1, Math.min(dp[i+1][j]-dungeon[i][j], dp[i][j+1]-dungeon[i][j]));
}
}
return dp[0][0];
}
}``````

• short explain:

dp from bottom-right to top-left

we create the matrix dp[i][j] represent the "LEAST HEALTH" for knight when enter into the dungeon[i][j]

then we got the equtation:

dp[i][j] >= 1 AND ( dp[i][j] - dungeon[i][j] >= dp[i+1][j] OR dp[i][j] - dungeon[i][j] >= dp[i][j+1] )

initial the bottom and right most line, start iteration, got result in dp[0][0]

• Nice Solution

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