<p>The demons had captured the princess and imprisoned her in <strong>the bottom-right corner</strong> of a <code>dungeon</code>. The <code>dungeon</code> consists of <code>m x n</code> rooms laid out in a 2D grid. Our valiant knight was initially positioned in <strong>the top-left room</strong> and must fight his way through <code>dungeon</code> to rescue the princess.</p>

<p>The knight has an initial health point represented by a positive integer. If at any point his health point drops to <code>0</code> or below, he dies immediately.</p>

<p>Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight&#39;s health (represented by positive integers).</p>

<p>To reach the princess as quickly as possible, the knight decides to move only <strong>rightward</strong> or <strong>downward</strong> in each step.</p>

<p>Return <em>the knight&#39;s minimum initial health so that he can rescue the princess</em>.</p>

<p><strong>Note</strong> that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/13/dungeon-grid-1.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
<strong>Output:</strong> 7
<strong>Explanation:</strong> The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-&gt; RIGHT -&gt; DOWN -&gt; DOWN.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> dungeon = [[0]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == dungeon.length</code></li>
	<li><code>n == dungeon[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>-1000 &lt;= dungeon[i][j] &lt;= 1000</code></li>
</ul>

class Solution {
public:
    void f(vector<vector<int>>& dungeon, int i, int j, int m, int n, int cur, 
    int curMin, int &ans)
    {
        if(i >= m || j >= n)
            return;
        int sum = cur + dungeon[i][j];
        curMin = min(sum, curMin);
        if(i == m-1 && j == n-1)
        {
            if(curMin > ans)
                ans = curMin;
            return;
        }
        if(curMin < ans)
            return;
        f(dungeon, i+1, j, m, n, sum, curMin, ans);
        f(dungeon, i, j+1, m, n, sum, curMin, ans);
    }
    int g(vector<vector<int>>& dungeon, int i, int j, int m, int n, vector<vector<int>> &dp)
    {
        if(i>=m || j>=n)
            return INT_MIN;
        if(i == m-1 && j == n-1)
        {
            if(dungeon[i][j] > 0)
                return dp[i][j] = 0;
            else
                return dp[i][j] = dungeon[i][j];
        }
        if(dp[i+1][j] == INT_MIN)
            dp[i+1][j] = g(dungeon, i+1, j, m, n, dp);
        if(dp[i][j+1] == INT_MIN)
            dp[i][j+1] = g(dungeon, i, j+1, m, n, dp);

        int maxAdj = max(dp[i+1][j], dp[i][j+1]);
        dp[i][j] = dungeon[i][j] + maxAdj;
        if(dp[i][j] > 0)
            dp[i][j] = 0;
        return dp[i][j];
    }
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        /*
        // Recursive soln gives TLE
        int ans = INT_MIN;
        f(dungeon, 0, 0, m, n, 0, 0, ans);
        cout<<ans;
        if(ans > 0)
            return 1;
        return (-ans) + 1;
        */


        vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MIN));
        return abs(g(dungeon, 0, 0, m, n, dp)) + 1;

        /*
        // Expl: https://www.youtube.com/watch?v=4uUGxZXoR5o
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[m-1][n-1] = dungeon[m-1][n-1];
        if(dp[m-1][n-1] > 0)
            dp[m-1][n-1] = 0;
        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 maxAdj = -1e9;
                if(j+1 < n)
                    maxAdj = max(maxAdj, dp[i][j+1]);
                if(i+1 < m)
                    maxAdj = max(maxAdj, dp[i+1][j]);
                dp[i][j] = dungeon[i][j] + maxAdj;
                if(dp[i][j] > 0)
                    dp[i][j] = 0;
            }
        }
        return abs(dp[0][0]) + 1;
        */
    }
};
11800