Binary Search, DFS and DP

174. Dungeon Game

The naively DFS solution gets TLE as each position we have two choices and it will make the complexity exponential.

class Solution:
    def calculateMinimumHP(self, a: List[List[int]]) -> int:
        R, C = len(a), len(a[0])
        dp = [[0]*C for _ in range(R)]
        hi = [sum([r for r in row if r<0]+[0]) for row in a]
        if not hi:return 1
        else: hi = sum(hi)
        lo, hi = 1, -hi+1
        from functools import lru_cache
        @lru_cache(None)
        def dfs(m, i, j):
            if i>=R or j>=C or m+a[i][j]<=0:return False
            if i==R-1 and j==C-1:return True
            left = dfs(m+a[i][j], i, j+1 )
            right = dfs(m+a[i][j], i+1, j)
            return left or right
        while lo < hi:
            mid = (lo+hi)//2
            if dfs(mid, 0, 0):
                hi = mid
            else:
                lo = mid+1
        return lo

The modified maximum path and binary search work pretty good.

# time complexity O(RC log MAX_VAL) where the MAX_VAL is the maximum possible value to try, it is the hi in the code.
# Space complexity O(RC)
class Solution:
    def calculateMinimumHP(self, a: List[List[int]]) -> int:
        R, C = len(a), len(a[0])
        hi = [sum([r for r in row if r<0]+[0]) for row in a]
        if not hi:return 1
        else: hi = sum(hi)
        lo, hi = 1, -hi+1
        
        def dp(mid):
            dp = [[-float('inf')]*C for _ in range(R)]
            dp[0][0] = mid + a[0][0]
            if dp[0][0]<=0:return False
            # update first row
            for i in range(1, R):
                this_val = dp[i-1][0]+a[i][0]
                if this_val<=0:break
                dp[i][0] = this_val
        
            # update first col
            for j in range(1, C):
                this_val = dp[0][j-1]+a[0][j]
                if this_val<=0:break
                dp[0][j] = this_val
           
            # update the rest
            for i in range(1, R):
                for j in range(1, C):
                    this_val = max(dp[i][j-1], dp[i-1][j])+a[i][j]
                    if this_val > 0:dp[i][j] = this_val
            return dp[R-1][C-1]>0 
                                 
        while lo < hi:
            mid = (lo+hi)//2
            if dp(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

Actually, we can use a simple DP to solve this problem. The solution is shown HERE.

Python version is here:

class Solution:
    def calculateMinimumHP(self, a: List[List[int]]) -> int:
        R, C = len(a), len(a[0])
        dp = [[float("inf")]*(C+1) for _ in range(R+1)]
        dp[R][C-1] = dp[R-1][C]= 1
        for i in range(R)[::-1]:
            for j in range(C)[::-1]:
                needed = min(dp[i+1][j], dp[i][j+1])-a[i][j]
                dp[i][j]= needed if needed>0 else 1
        return dp[0][0]