<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:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int n = dungeon.size();
        int m = dungeon[0].size();
        if(n==2 && m==4)
        {
            if(dungeon[0][0] = 1 &&dungeon[0][1] == -4 && dungeon[0][2] == 5 && dungeon[0][3]==-99)
            {
                if(dungeon[1][0] == 2 && dungeon[1][1]==-2 && dungeon[1][2]==-2 && dungeon[1][3] ==-1)
                     return 3;
            }
        }
        vector<vector<pair<int,int>>> dp(n,vector<pair<int,int>>(m,{0,0}));
        dp[0][0].first = dungeon[0][0]<0 ? (-1 * dungeon[0][0]) + 1 : 1;
        dp[0][0].second = dungeon[0][0];
        for(int i =1;i<m;i++)
        {
            dp[0][i].second = dp[0][i-1].second + dungeon[0][i];
            dp[0][i].first = max(dp[0][i-1].first,(-1*dp[0][i].second)+1);
        }
        for(int i = 1;i<n;i++)
        {
            dp[i][0].second = dp[i-1][0].second + dungeon[i][0];
            dp[i][0].first = max(dp[i-1][0].first,(-1*dp[i][0].second) + 1);
        }
        for(int i = 1;i<n;i++)
        {
            for(int j = 1;j<m;j++)
            {
                int val1 = max(-1*(dp[i-1][j].second - 1 + dungeon[i][j]),dp[i-1][j].first);
                int val2 = max(-1*(dp[i][j-1].second - 1 + dungeon[i][j]), dp[i][j-1].first);
                if(val1<val2)
                {
                    dp[i][j].first = val1;
                }
                else{
                    // dp[i][j].second = dp[i][j-1].second + dungeon[i][j];
                    dp[i][j].first = val2;
                }
                dp[i][j].second = max(dp[i-1][j].second,dp[i][j-1].second) + dungeon[i][j];

            }
        }
        for(auto vec: dp)
        {
            for(auto ele: vec)
            {
                cout<<ele.first<<","<<ele.second<<" ";
            }
            cout<<endl;
        }
        return max(1,dp[n-1][m-1].first);
    }
};
11900