<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:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        """
        7:14
        11:00
        11:17

        DP
        O(nm)
        """
        self.dungeon = dungeon
        self.height = len(dungeon)
        self.width = len(dungeon[0])
        return self.calculateMinimumHPHelper(0,0,{})
        # return max((-options[1][1]) + 1, 1)

    def calculateMinimumHPHelper(self, i, j, memo):
        """
        memo will store - 

        the minimum hp we need from this point forward
        which will be at least 1

        """
        key = (i,j)
        if key in memo:
            return memo[key]

        if i >= self.height:
            return float("inf")
        if j >= self.width:
            return float("inf")

        val = self.dungeon[i][j]
        if i == self.height-1 and j == self.width-1:
            memo[key] = max(-val+1, 1)
            return memo[key]
        
        right = self.calculateMinimumHPHelper(i, j+1, memo)
        down = self.calculateMinimumHPHelper(i+1, j, memo)
        memo[key] = max(1, min(right, down)-val)
        return memo[key]

    # def calculateMinimumHPHelper(self, i, j, memo):
    #     """
    #     memo will store two tuples
    #     (
    #         (best_current_health, corresponding_worst_health_in_path)
    #         (current_health, best_corresponding_worst_health_in_path)
    #     )
    #     the best health loss from this point forward and the 
    #     worst health loss along the best path forward
    #     """
    #     key = (i,j)
    #     if key in memo:
    #         return memo[key]
        
    #     if i >= self.height:
    #         return [(-float("inf"), -float("inf")), (-float("inf"), -float("inf"))]
    #     if j >= self.width:
    #         return [(-float("inf"), -float("inf")), (-float("inf"), -float("inf"))]
       
    #     val = self.dungeon[i][j]
    #     if i == self.height-1 and j == self.width-1:
    #         memo[key] = [(val, val), (val, val)]
    #         return memo[key]

    #     possibilities = []
    #     possibilities.extend(self.calculateMinimumHPHelper(i, j+1, memo))
    #     possibilities.extend(self.calculateMinimumHPHelper(i+1, j, memo))

    #     options = []
    #     for [curr, worst] in possibilities:
    #         options.append((min(val, val+curr), min(val+curr, val, worst)))
    #     # print("Here options", i, j, options)
    #     options.sort(key=lambda x: x[0])
    #     best_curr = options[-1]

    #     options.sort(key=lambda x: x[1])
    #     best_worst = options[-1]
    #     memo[key] = (best_curr, best_worst)
        

    #     # if i == self.height-1:
    #     #     right_curr, right_worst = self.calculateMinimumHPHelper(i, j+1, memo)
    #     #     new_curr = self.dungeon[i][j] + right_curr
    #     #     memo[key] = new_curr, min(new_curr, right_worst)
    #     #     return memo[key]
    #     # if j == self.width-1:
    #     #     down_curr, down_worst = self.calculateMinimumHPHelper(i, j+1, memo)
    #     #     memo[key] = self.dungeon[i][j] + self.calculateMinimumHPHelper(i+1, j, memo)
    #     #     return memo[key]
    #     # right = self.dungeon[i][j] + self.calculateMinimumHPHelper(i, j+1, memo)
    #     # down = self.dungeon[i][j] + self.calculateMinimumHPHelper(i+1, j, memo)
    #     # memo[key] = max(right, down)
    #     return memo[key]
        
        

        
19100