# 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]`

--

--

## More from Jimmy (xiaoke) Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.