# Java Solution using DP

• Given the health of knight cannot be allowed to be less than 1, and we want to calculate the min-health at the start, so we should iterate the dp array in reverse order.
For each cell, if the dungeon[i][j] is positive, dp[i][j] subtracts it until 1; if the dungeon[i][j] is negative, dp[i][j] plus it. Because the knight can only move right or down, so the value of each cell in dp comes from the min value of its right and bottom cell.

``````public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int[][] dp = new int[dungeon.length][dungeon[0].length];

for(int i=dp.length-1; i>=0; i--) {
for(int j=dp[0].length-1; j>=0; j--) {
if(i == dp.length-1 && j == dp[0].length-1) {
dp[i][j] = 1 - dungeon[i][j] < 1 ? 1 : 1 - dungeon[i][j];
} else {
int right = j == dp[0].length-1 ? Integer.MAX_VALUE :
(dp[i][j+1] - dungeon[i][j] < 1 ? 1 : dp[i][j+1] - dungeon[i][j]);
int bottom = i == dp.length-1 ? Integer.MAX_VALUE :
dp[i+1][j] - dungeon[i][j] < 1 ? 1 : dp[i+1][j] - dungeon[i][j];
dp[i][j] = Math.min(right, bottom);
}
}
}
return dp[0][0];
}
}
``````

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