2022-01-08 13:40:01
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
def oneIfNotPos(a):
return a if a > 0 else 1
def f(i: int, j: int) -> int:
cached = self.cache.get((i, j))
if cached:
return cached
answer = min(oneIfNotPos(f(i, j + 1) - dungeon[i][j]), \
oneIfNotPos(f(i + 1, j) - dungeon[i][j]))
self.cache[(i, j)] = answer
return answer
m = len(dungeon)
n = len(dungeon[0])
# init cache to remove ifs from f
self.cache = {(m - 1, n - 1): oneIfNotPos(1 - dungeon[m - 1][n - 1])}
for i in range(0, m):
self.cache[(i, n)] = 1000 000000 # inf
for j in range(0, n):
self.cache[(m, j)] = 10000 00000 # inf
return f(0, 0)
Python
Dungeon Hunters
Telegram - https://t.me/getcode1
915 views10:40
C
