<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) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        int m=dungeon.size(),n=dungeon[0].size(),si=m-1,sj=n-2;
        if (n==1){
            int h=1,min=0;
            for (int i=0;i<m;i++){
                h+=dungeon[i][0];
                if (h<=0 && min<-h+1) min=-h+1;
            }
            if (min==0) return 1;
            return min+1;
        }
        int min[m][n];
        if(dungeon[m-1][n-1]>=0) min[m-1][n-1]=0;
        else min[m-1][n-1]=-dungeon[m-1][n-1];
        for (int v=0;v<m+n-2;v++){
            int i=si,j=sj;
            while(i!=-1 && j!=n){
                if (dungeon[i][j]>=0){
                    min[i][j]=999999;
                    if (i!=m-1){
                        if (dungeon[i][j]>=min[i+1][j]){
                            min[i][j]=0;
                        }else{
                            min[i][j]=min[i+1][j]-dungeon[i][j];
                        }
                    }
                    if (j!=n-1){
                        if (dungeon[i][j]>=min[i][j+1]){
                            min[i][j]=0;
                        }else{
                            if (min[i][j]>min[i][j+1]-dungeon[i][j]) min[i][j]=min[i][j+1]-dungeon[i][j];
                        }
                    }
                }else{
                    min[i][j]=9999999;
                    if (i!=m-1){
                        if (min[i+1][j]>=0) min[i][j]=min[i+1][j]-dungeon[i][j];
                        else min[i][j]=-dungeon[i][j];
                    }
                    if (j!=n-1){
                        if (min[i][j+1]>=0) {
                            if (min[i][j]>min[i][j+1]-dungeon[i][j]) min[i][j]=min[i][j+1]-dungeon[i][j];
                        }
                        else {
                            if (min[i][j]>-dungeon[i][j]) min[i][j]=-dungeon[i][j];
                        }
                    }
                }
                i--;
                j++;
            }
            if (sj) sj--;
            else si--;
        }
        return 1+min[0][0];
    }
};
11400