import queue
from typing import List
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
# M and N are dimensions of the dungeon
M = len(dungeon)
N = len(dungeon[0])
# create a dp matrix for dungeon
dp = [[0]*N for _ in range(M)]
# from right-bot to left-top
for i in range(M-1, -1, -1):
for j in range(N-1, -1, -1):
if i == M-1 and j == N-1:
# at (M-1, N-1) you at least need 1 hp left
dp[M - 1][N - 1] = 1
elif i == M-1 and j != N-1:
# at (M-1, j) you need at least 1 hp to be alive, and you need prepare at least
# dp[i][j+1] - dungeon[i][j+1] hp to go right cell
dp[M-1][j] = max(1, dp[i][j+1] - dungeon[i][j+1])
elif i != M-1 and j == N-1:
# at (i, N-1) you need at least 1 hp to be alive, and you need prepare at least
# dp[i+1][j] - dungeon[i+1][j] hp to go bot cell
dp[i][j] = max(1, dp[i+1][j] - dungeon[i+1][j])
else:
# at (i, j) upi need at least dp[i + 1][j] - dungeon[i + 1][j] hp to go bot cell and
# dp[i][j+1] - dungeon[i][j+1] hp to go right cell. Also at cell (i, j) you need at least 1 hp.
dp[i][j] = max(1, min(dp[i + 1][j] - dungeon[i + 1][j], dp[i][j+1] - dungeon[i][j+1]))
# you must go through (0, 0) cell, which is not calculated above.
return max(1, dp[0][0] - dungeon[0][0])
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)