Dungeon Game

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of MxN rooms laid out in a 2D grid. Our valiant knight was initially positioned at the top-left corner of the dungeon. The knight needs to reach the princess. The knight has a certain amount of health. If at any point his health drops to 0 or below, he will die and we lose. Some of the rooms in the dungeon contain magic, which either increases or decreases the knight's health. At each cell, the knight can only move either right or down. Find the minimum amount of health the knight needs to have initially so that he will not die in the dungeon.

int calculateMinimumHP(vector<vector<int>>& dungeon) {
  int rows = dungeon.size(), cols = dungeon[0].size();
  vector<vector<int>> dp(rows, vector<int>(cols));
  dp[rows-1][cols-1] = max(1, 1 - dungeon[rows-1][cols-1]);
  for (int i = rows-2;
  i >= 0;
  i--) {
    dp[i][cols-1] = max(1, dp[i+1][cols-1] - dungeon[i][cols-1]);
  }
  for (int j = cols-2;
  j >= 0;
  j--) {
    dp[rows-1][j] = max(1, dp[rows-1][j+1] - dungeon[rows-1][j]);
  }
  for (int i = rows-2;
  i >= 0;
  i--) {
    for (int j = cols-2;
    j >= 0;
    j--) {
      dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]);
    }
  }
  return dp[0][0];
}