```
public class Solution {
public int CalculateMinimumHP(int[,] dungeon) {
int rows = dungeon.GetLength(0);
int cols = dungeon.GetLength(1);
// save partial solutions in a matrix
int[,] solutions = new int[rows, cols];
// start with last room in the dungeon and ask the following question:
// what would the minimum health of the Knight need to be so he can survive the last room?
// Answer: if the room has a devil (negative value) than his health needs to be at least 1 above
// the devil's strength. Otherwise (room is empty or has a magic orb) his health only needs to be equal to 1
// Therefore, we can set his health to the max value between 1 and 1 - dungeon[rows - 1, cols - 1]
int bottomRow = rows - 1;
int rightCol = cols - 1;
solutions[bottomRow, rightCol] = Math.Max(1, 1 - dungeon[bottomRow, rightCol]);
// now that we know the Knight's minimal health required in the last room, we can compute his minimal health
// in other rooms. For each room he enters, he needs to be strong enough to survie that room AND meet the minimum
// health required in the next room immediately after that. Since there are two rooms immediately after (except
// for when his is at the borders), we compute both of those health values and keep the smaller one (because we want the
// minumum health required)
// first, we take care of the borders (bottom row and right column)
// right column: traverse the rooms from the bottom to the top and make sure the Knight is strong enough to survive the room
// AND arrive at the next room (on its bottom side) with a health greater than or equal to solutions[i + 1, rightCol]
for (int i = bottomRow - 1; i >= 0; i--) {
solutions[i, rightCol] = Math.Max(1, solutions[i + 1, rightCol] - dungeon[i, rightCol]);
}
// bottom row: traverse the rooms from right to left and make sure the Knight is strong enough to survive the room AND arrive
// at the next room (on its right side) with a health greater than or equal to solutions[bottomRow, j + 1]
for (int j = rightCol - 1; j >= 0; j--) {
solutions[bottomRow, j] = Math.Max(1, solutions[bottomRow, j + 1] - dungeon[bottomRow, j]);
}
// now, take care of the inner dungeon. Each room has now two neighboring rooms (to the right and down), so we need
// to compute the minimum health with respect to each of them. We then take the minimum value.
for (int i = bottomRow - 1; i >= 0; i--) {
for (int j = rightCol - 1; j >= 0; j--) {
//compute min health to survive this room AND room to the right
int minRight = Math.Max(1, solutions[i, j + 1] - dungeon[i, j]);
//compute min health to survie this room AND room down to the bottom
int minDown = Math.Max(1, solutions[i + 1, j] - dungeon[i, j]);
//take min of the two
solutions[i, j] = Math.Min(minRight, minDown);
}
}
// our solution is the minimal health the Knight needs to have in the very first room (0,0)
return solutions[0, 0];
}
}
```