Участник:Polina Potapova/dungeon-game

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/dungeon-game/

class Solution(object):
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        M = len(dungeon)
        N = len(dungeon[0])
 
        plan = [[0 for i in range(N)] for j in range(M)]
        plan[M - 1][N - 1] = max(1, 1 - dungeon[M - 1][N - 1])
 
        for row in reversed(range(M - 1)):
            plan[row][N - 1] = max(1, plan[row + 1][N - 1] - dungeon[row][N - 1])
        for column in reversed(range(N - 1)):
            plan[M - 1][column] = max(1, plan[M - 1][column + 1] - dungeon[M - 1][column])
        for row in reversed(range(M - 1)):
            for column in reversed(range(N - 1)):
                plan[row][column] = max(1, min(plan[row + 1][column], plan[row][column + 1]) - dungeon[row][column])
 
        return plan[0][0]