# 174. Dungeon Game

`class Solution:    def calculateMinimumHP(self, a: List[List[int]]) -> int:        R, C = len(a), len(a)        dp = [*C for _ in range(R)]        hi = [sum([r for r in row if r<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`
`# 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)        hi = [sum([r for r in row if r<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 = mid + a            if dp<=0:return False            # update first row            for i in range(1, R):                this_val = dp[i-1]+a[i]                if this_val<=0:break                dp[i] = this_val                    # update first col            for j in range(1, C):                this_val = dp[j-1]+a[j]                if this_val<=0:break                dp[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`
`class Solution:    def calculateMinimumHP(self, a: List[List[int]]) -> int:        R, C = len(a), len(a)        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`

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi