Сложность: hard
Демоны поймали принцессу и заперли её в самой нижней правой комнате подземелья. Подземелье состоит из комнат, расположенных в форме сетки размером m x n. Наш отважный рыцарь изначально находится в комнате в верхнем левом углу и должен пробиться через подземелье, чтобы спасти принцессу.
Рыцарь имеет начальный запас здоровья, представленный положительным целым числом. Если в какой-то момент его уровень здоровья упадет до 0 или ниже, он умирает мгновенно.
Некоторые комнаты охраняются демонами (представлены отрицательными числами), так что рыцарь теряет здоровье, входя в эти комнаты; другие комнаты либо пусты (обозначены как 0), либо содержат магические сферы, которые увеличивают здоровье рыцаря (представлены положительными числами).
Чтобы как можно скорее добраться до принцессы, рыцарь решает двигаться только вправо или вниз на каждом шаге.
Верните минимальное начальное здоровье рыцаря, необходимое для того, чтобы он мог спасти принцессу.
Обратите внимание, что любая комната может содержать угрозы или усилители, даже первая комната, в которую входит рыцарь, и нижняя правая комната, где заключена принцесса.
Пример:
Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.
👨💻 Алгоритм:
1️⃣Определение матрицы dp: Создайте матрицу dp размером с подземелье, где элемент dp[row][col] указывает минимальное количество здоровья, необходимое рыцарю, чтобы начать путь из ячейки dungeon[row][col] и достигнуть цели (нижней правой ячейки).
2️⃣Инициализация и заполнение dp: Начните с правого нижнего угла подземелья и идите в обратном направлении — справа налево и снизу вверх. Для каждой ячейки вычислите соответствующее значение в dp: Если возможно, шаг вправо из текущей ячейки подземелья требует right_health здоровья. Если возможно, шаг вниз из текущей ячейки подземелья требует down_health здоровья. Возьмите минимальное значение из right_health и down_health для dp[row][col]. Если ни один из вышеперечисленных вариантов не доступен (то есть вы находитесь в ячейке назначения), учитывайте два подслучая: Если в ячейке магический шар, достаточно 1 единицы здоровья. Если в ячейке демон, рыцарю необходимо иметь единицу здоровья плюс урон, который может нанести демон.
3️⃣Результат вычислений: Значение в dp[0][0] будет указывать на минимальное количество здоровья, необходимое рыцарю, чтобы начать свой путь из верхней левой ячейки подземелья и успешно спасти принцессу, учитывая все угрозы на его пути.
😎 Решение:
class Solution(object):
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
rows, cols = len(dungeon), len(dungeon[0])
dp = [[float("inf")] * cols for _ in range(rows)]
def get_min_health(currCell: int, nextRow: int, nextCol: int) -> float:
if nextRow >= rows or nextCol >= cols:
return float("inf")
nextCell = dp[nextRow][nextCol]
# hero needs at least 1 point to survive
return max(1, nextCell - currCell)
for row in reversed(range(rows)):
for col in reversed(range(cols)):
currCell = dungeon[row][col]
right_health = get_min_health(currCell, row, col + 1)
down_health = get_min_health(currCell, row + 1, col)
next_health = min(right_health, down_health)
if next_health != float("inf"):
min_health = next_health
else:
min_health = 1 if currCell >= 0 else (1 - currCell)
dp[row][col] = min_health
return dp[0][0]
Ставь 👍 и забирай 📚 Базу знаний