Binary Search, DFS and DP

174. Dungeon Game

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

Data Scientist/MLE/SWE @takemobi