text: /*
  Problem Statement: https://leetcode.com/problems/dungeon-game/
  Time: O(m • n)
  Space: O(m • n)
  Author: Mohammed Shoaib, github.com/Mohammed-Shoaib
  */
  
  class Solution {
  public:
  	int calculateMinimumHP(vector<vector<int>>& dungeon) {
  		int m, n;
  		m = dungeon.size();
  		n = dungeon[0].size();
  		int dp[m][n];
  		
  		// initialization
  		dp[m - 1][n - 1] = min(0, dungeon[m - 1][n - 1]);
  		for (int i = m - 2; i >= 0; i--)
  			dp[i][n - 1] = min(0, dungeon[i][n - 1] + dp[i + 1][n - 1]);
  		for (int i = n - 2; i >= 0; i--)
  			dp[m - 1][i] = min(0, dungeon[m - 1][i] + dp[m - 1][i + 1]);
  		
  		// dynamic programming
  		for (int i = m - 2; i >= 0; i--)
  			for (int j = n - 2; j >= 0; j--)
  				dp[i][j] = min(0, dungeon[i][j] + max(dp[i + 1][j], dp[i][j + 1]));
  		
  		return abs(dp[0][0]) + 1;
  	}
  };