https://leetcode.com/problems/dungeon-game

Probably when you see this problem and you have some experience in this type of problems you can guess, that this is dynamic programming problem. However even if you understand this, it is not easy to solve it. Let us use top-down dp, that is Let dp[i][j] be the minimum hp we need to reach the princess if we start from point (i,j). Let us consider the following example:

-2 -3 +3
-5 -10 +1
+10 +30 -5

Let us add bottom dummy row and right dummy column to handle border cases more easy. We fill it with infinities, except two ones - neibours of our princess. I will explain it a bit later.

How we can evaluate dp[i][j]? We need to look at two cells: dp[i+1][j] and dp[i][j+1] and evaluate two possible candidates: dp[i+1][j]-dungeon[i][j] and dp[i][j+1]-dungeon[i][j].

  1. If at least one of these two numbers is negative, it means that we can survive just with 1 hp: (look at number +30 in our table for example)
  2. If both this numbers are positive, we need to take the mimumum of them, see for example number -10 in our table: to survive we need either 5- -10 = 15 if we go right and 1- -10 = 11 if we go down, of course we choose 11.
  3. This conditions can be written in one a bit ugly line: dp[i][j] = max(min(dp[i+1][j],dp[i][j+1])-dungeon[i][j],1).
  4. Finally, why I put 1 to two neibors of princess? To make this formula valid for princess cell: if we have negative number like -5 in this cell, we need 6 hp to survive, if we have non-negative number in this cell, we need 1 hp to survive.
7 5 2 inf
6 11 5 inf
1 1 6 1
inf inf 1 #

Complexity: both time and space is O(mn). Space complexity can be reduced to O(min(m,n)) as usual, because we look only to neibour cells. However code becomes a bit more difficult to follow.

class Solution:
    def calculateMinimumHP(self, dungeon):
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float("inf")]*(n+1) for _ in range(m+1)]
        dp[m-1][n], dp[m][n-1] = 1, 1
            
        for i in range(m-1,-1,-1):
            for j in range(n-1,-1,-1):
                dp[i][j] = max(min(dp[i+1][j],dp[i][j+1])-dungeon[i][j],1)
        
        return dp[0][0]

Further discussion It is possible to do it with down-top dp as well, howerer in this case you need to use binary search, because you do not know in advance if you survive starting say 1000 hp or not. Complexity will be O(nm log(MAX_INT)) in this case.

If you like the solution, you can upvote it on leetcode discussion section: Problem 0174