174. Dungeon Game

This is very similar to "Minimum Path Sum" problem. The trick here is to calculate the health in the beginning we need start from bottom-right to top-left so that we can greedily minimize the health. Also, after calculation, if there is more health left, we only need to put the minimum number 1 in that state.

1:  class Solution {  
2:  public:  
3:    int calculateMinimumHP(vector<vector<int>>& dungeon) {  
4:      int rows = dungeon.size();  
5:      int cols = dungeon[0].size();  
6:      vector<vector<int>> dp(rows+1, vector<int>(cols+1, INT_MAX));  
7:      dp[rows-1][cols] = 1;  
8:      dp[rows][cols-1] = 1;  
9:      for (int i = rows-1; i >= 0; i--) {  
10:        for (int j = cols-1; j >= 0; j--) {  
11:          int hp = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];  
12:          dp[i][j] = (hp <= 0) ? 1 : hp;  
13:        }  
14:      }  
15:      return dp[0][0];  
16:    }  
17:  };