# Dungeon Game

This problem is suitable for a dynamic programing problem. Let be the minimum HP the knight need to enter first and from that cell to reach he princess. Of course to enter the right bottom cell where the princess stays we need at least . When performing dynamic programing iteration we ignore that at first the knight's HP must be at least 1. Then if the knight can start from entering and reach the target cell he must can also start from to either or DP[i][j]DP to get the final answer.

public class DungeonGame {
public int calculateMinimumHP(int[][] dungeon) {
if (dungeon.length == 0 || dungeon.length == 0) return 1;

int m = dungeon.length;
int n = dungeon.length;

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

for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (i == m - 1 && j == n - 1) continue;

int bottom = (i + 1 >= m) ? Integer.MAX_VALUE : dungeon[i + 1][j];
int right = (j + 1 >= n) ? Integer.MAX_VALUE : dungeon[i][j + 1];
dungeon[i][j] = Math.min(bottom, right) - dungeon[i][j];
dungeon[i][j] = Math.max(0, dungeon[i][j]);
}
}

return dungeon + 1;
}
}